For this study, we evaluated two training interventions for improving gait parameters in individuals with poststroke hemiplegia using a training methodology that required them to step over objects. Gait velocity, step length, ability to step over obstacles, and walking endurance were compared before and after 2 weeks of training and 2 weeks after cessation of training. Twenty subjects with poststroke hemiplegia completed six intervention sessions in which they were asked to step over either virtual objects while walking on a motorized treadmill or real foam objects on a 10 m walkway. With the virtual object training, if either foot collided with the virtual object, a tone sounded and a vibrotactile stimulus was applied to the colliding foot. All subjects tolerated the training sessions well, and no incidences of falling or undue cardiovascular responses occurred. The virtual obstacle training generated greater improvements in gait velocity compared with real training (20.5% vs. 12.2% improvement) during the fast walk test (p < 0.01). Improvements in gait velocity for both training methods were similar in the self-selected walk test (33.3% vs. 34.7% improvement). Overall, subjects showed clinically meaningful changes in gait velocity, stride length, walking endurance, and obstacle clearance capacity as a result of either training method. These changes persisted for 2 weeks posttraining. The inclusion of enhanced safety and visual augmentation may be responsible for the effectiveness of the virtual object intervention. These results demonstrate preliminary evidence for clinical effectiveness of obstacle training for improving gait velocity poststroke. In addition, these results provide evidence for enhanced clinical performance with virtual obstacle training.