Walking-In-Place (WIP) techniques make it possible to facilitate relatively natural locomotion within immersive virtual environments that are larger than the physical interaction space. However, in order to facilitate natural walking experiences one needs to know how to map steps in place to virtual motion. This paper describes two within-subjects studies performed with the intention of establishing the range of perceptually natural walking speeds for WIP locomotion. In both studies, subjects performed a series of virtual walks while exposed to visual gains (optic flow multipliers) ranging from 1.0 to 3.0. Thus, the slowest speed was equal to an estimate of the subjects normal walking speed, while the highest speed was three times greater. The perceived naturalness of the visual speed was assessed using self-reports. The first study compared four different types of movement, namely, no leg movement, walking on a treadmill, and two forms of gestural input for WIP locomotion. The results suggest that WIP locomotion is accompanied by a perceptual distortion of the speed of optic flow. The second study was performed using a 4×2 factorial design and compared four different display field-of-views (FOVs) and two types of movement, walking on a treadmill and WIP locomotion. The results revealed significant main effects of both movement type and field of view, but no significant interaction between the two variables. Particularly, they suggest that the size of the display FOV is inversely proportional to the degree of underestimation of the virtual speeds for both treadmill-mediated virtual walking and WIP locomotion. Combined, the results constitute a first attempt at establishing a set of guidelines specifying what virtual walking speeds WIP gestures should produce in order to facilitate a natural walking experience.