Signals from millisecond pulsars travel to us on geodesics along the line-of-sight that are affected by the space–time metric. The exact path-geometry and redshifting along the geodesics determine the observed Time-of-Arrival (ToA) of the pulses. The metric is determined by the distribution of dark matter, gas, and stars in the galaxy and, in the final stages of travel, by the distribution of solar system bodies. The inhomogeneous distribution of stellar masses can have a small but significant statistical effect on the ToAs through the perturbation of geodesics. This will result in additional noise in ToA observations that may affect Pulsar Timing Array (PTA) constraints on gravitational waves at very low frequencies. We employ a simple model for the stellar distribution in our galaxy to estimate the scale of both static and dynamic sources of what we term generically “geodesic noise”. We find that geodesic noise has a standard deviation of (10) ns for typical lines-of-sight. This suggests geodesic noise is relevant for estimates of PTA sensitivity and may limit future efforts for detection of gravitational waves by PTAs.