The distance to the black hole binary GX 339-4 remains a topic of debate. We examine high-resolution optical spectra of the Na D lines resolving the velocity structure along the line of sight. We find this to be complex, with at least nine components, mostly blueshifted, spanning a velocity range of nearly 200 km s-1. The presence of components with a large blueshift rules out a nearby location and requires that the binary be located at or beyond the tangent point, implying a lower limit to the distance of ~6 kpc. The presence of a significant redshifted component at +30 km s-1 is even more intriguing, as GX 339-4 also has a slightly positive systemic velocity, suggesting that the source, and this cloud, could be on the far side of the Galaxy, where the radial velocities due to Galactic rotation become positive again. If this is the case, we require a distance of ~15 kpc. This is less secure than the 6 kpc lower limit, however. We discuss the implications of these possible distances for the outburst and quiescent luminosities, as well as the nature of the companion star, and argue that a large distance explains these characteristics. In particular, it would explain the nondetection of the companion star during the faintest states.