Judging distances is crucial when interacting with the environment. For short distances in action space (up to 30 m), both explicit verbal estimates and locomotor judgments are fairly accurate. For large distances, data have remained scarce. In two laboratory experiments, our observers judged distances to visual targets presented stereoscopically, either by giving a verbal estimate or by walking the distance to the target on a treadmill. While verbal judgments remained linearly scaled over the whole range of distances from 20 to 262 m, locomotor judgments fell short at distances above 100 m, indicating that observers overestimated the distance they had traveled and increasingly did so as a function of actual target distance. This pattern persisted when controlling for the potential confound of fatigue or reluctance to walk. We discuss different approaches to explain our findings and stress the importance of a differential use of distance cues. A model of leaky path integration showed a good fit with our locomotor data.