Einstein’s gravity has been extensively tested in the weak field regime, primarily with experiments in the Solar System and observations of binary pulsars, and current data agree well with theoretical predictions. On the other hand, strong gravity is largely unexplored and there are a number of theories beyond Einstein’s gravity that make the same predictions for weak fields and present deviations only when gravity becomes strong. The best laboratory for testing strong gravity is the spacetime around astrophysical black holes. X-ray reflection spectroscopy can be a powerful tool to probe the strong gravity region around astrophysical black holes and test the nature of these objects. In this paper, we will introduce RELXILL_NK, which is the first XSPEC reflection model to test Einstein’s gravity in the strong field regime, and we will present the constraints on possible deviations from Einstein’s gravity that we have obtained by analyzing Suzaku data of Ark 564.