One century after its formulation, Einstein's general relativity has made remarkable predictions and turned out to be compatible with all experimental tests. Most of these tests probe the theory in the weak-field regime, and there are theoretical and experimental reasons to believe that general relativity should be modified when gravitational fields are strong and spacetime curvature is large. The best astrophysical laboratories to probe strong-field gravity are black holes and neutron stars, whether isolated or in binary systems. We review the motivations to consider extensions of general relativity. We present a (necessarily incomplete) catalog of modified theories of gravity for which strong-field predictions have been computed and contrasted to Einstein's theory, and we summarize our current understanding of the structure and dynamics of compact objects in these theories. We discuss current bounds on modified gravity from binary pulsar and cosmological observations, and we highlight the potential of future gravitational wave measurements to inform us on the behavior of gravity in the strong-field regime.