In virtual reality, visual speed is usually underestimated relative to locomotor speed. Here we investigated how physical activity and fitness affect perceived visual speed when running in a treadmill-mediated virtual environment. Thirty healthy participants (ten sedentary individuals, ten team sport players and ten expert runners) ran on a treadmill at two different speeds (8, 12km/h) in front of a moving virtual scene. Participants were asked to match the speed of the visual scene to their running speed (i.e. treadmill speed), indicating for each trial whether the scene was moving slower or faster than the treadmill. The speed of the visual scene was adjusted according to the participant’s response using a staircase until visual and running speeds were perceived as equivalent. More sedentary participants underestimated visual speed relative to their actual running speed. Specifically, visual speed had to exceed running speed to be perceived as equivalent. The underestimation of visual speed was speed-dependent, and it was significantly larger for sedentary participants than for team sports players and expert runners. The volume of physical activity per week was found to be the best predictor of visual speed perception for both running speeds, while the perceived effort constituted a good predictor only at 8km/h. Physical fitness, on the other hand turned out to be a poor predictor of visual speed perception. Therefore, in order to enhance users’ engagement and their adherence to physical activity programs, the development of “personalized” treadmill-mediated virtual environments should take into account users’ personal characteristics to provide the most natural and engaging feedback possible.