Gravity curves space and time. This can lead to proper time differences between freely falling, nonlocal trajectories. A spatial superposition of a massive particle is predicted to be sensitive to this effect. We measure the gravitational phase shift induced in a matter-wave interferometer by a kilogram-scale source mass close to one of the wave packets. Deflections of each interferometer arm due to the source mass are independently measured. The phase shift deviates from the deflection-induced phase contribution, as predicted by quantum mechanics. In addition, the observed scaling of the phase shift is consistent with Heisenberg’s error-disturbance relation. These results show that gravity creates Aharonov-Bohm phase shifts analogous to those produced by electromagnetic interactions.