Newton’s law of gravity has a very simple mathematical form, and yet is accurate enough to understand most planetary orbits around the sun. Observation of the motion of Uranus led to postulate the existence of a new planet, Neptune, that was observed in 1846. A similar conclusion was expected from observation of the perihelion of Mercury, but ‘Vulcan’ was never observed, and the explanation came form a modified theory of gravity (see the wikipedia page), namely General Relativity.
General relativity was formulated in 1915 by A. Einstein, a bit less than 10 years after his theory of special relativity. The basic principle of GR is well summarized by the celebrated quote by J. A. Wheeler:
Spacetime tells matter how to move; matter tells spacetime how to curve’.
As we just mentioned, among the first success of GR was the correct prediction of Mercury’s perihelion advance. In 1919, Eddington and his collaborators measured the deflection of light around the sun during a total eclipse (in parallel to similar experiment in Brazil and west coast of Africa), and found that it agrees with the prediction of GR. See this page for more details on tests of GR.
GR has passed most of the current tests with flying colors. However most of these tests actually probe the weak field regime of gravity, and future experiments are expected to test gravity in strong regime. Let us mention an important test anyway (probably among the most important), namely this involving binary pulsars. The variation of the orbital period measured for instance in the Hulse-Taylor pulsar (leading to a Nobel Prize in 1993) was consistent with the one computed taking into account emission of gravitational waves within GR.
However, GR alone is not enough for understanding our universe at all scales. At cosmological scale, at least a cosmological constant and cold dark matter is required to understand the shape of the Cosmic MicroWave Background (see results of the Planck mission), and at the level of galaxy, unobserved matter is needed to recover the galactic rotation curves. This unseen form of matter can also be understood in terms of AMG.
See this recent review for astrophysical tests of GR.