Neutron stars and black holes are the astrophysical systems with the strongest gravitational fields in the universe. In this article, I review the prospect of using observations of such compact objects to probe some of the most intriguing general relativistic predictions in the strong-field regime: the absence of stable circular orbits near a compact object and the presence of event horizons around black-hole singularities. I discuss the need for a theoretical framework, within which future experiments will provide detailed, quantitative tests of gravity theories. Finally, I summarize the constraints imposed by current observations of neutron stars on potential deviations from general relativity.