Virtual Reality (VR) technology offers promising opportunities to improve traditional treadmill-based rehabilitation programs. We present an immersive VR rehabilitation system that includes a head-mounted display and motion sensors. The application is designed to promote the experience of relatedness, autonomy, and competence. The application uses procedural content generation to generate diverse landscapes. We evaluated the effect of the immersive rehabilitation system on motivation and affect. We conducted a repeated measures study with 36 healthy participants to compare the immersive program to a traditional rehabilitation program. Participants reported significant greater enjoyment, felt more competent and experienced higher decision freedom and meaningfulness in the immersive VR gait training compared to the traditional training. They experienced significantly lower physical demand, simulator sickness, and state anxiety, and felt less pressured while still perceiving a higher personal performance. We derive three design implications for future applications in gait rehabilitation: Immersive VR provides a promising augmentation for gait rehabilitation. Gamification features provide a design guideline for content creation in gait rehabilitation. Relatedness and autonomy provide critical content features in gait rehabilitation.