In contrast to gravity in the weak-field regime, which has been subjected to numerous experimental tests, gravity in the strong-field regime is largely unconstrained by experiments. Indeed, a large class of gravity theories can be constructed that obey the Einstein equivalence principle and cannot be rejected by solar system tests, but that diverge from general relativity in the strong-field regime. I discuss why such theories predict black holes and neutron stars with significantly different properties than their general relativistic counterparts. I then show how recent observations with current telescopes have provided interesting new constraints on scalar-tensor and braneworld gravity models that are comparable to solar-system and table-top experiments.