After stroke, the ability to make step adjustments during walking is reduced and requires more attention, which may cause problems during community walking. The C-Mill is an innovative treadmill augmented with visual context (e.g., obstacles and stepping targets), which was designed specifically to practice gait adaptability. The objective of this study was to determine whether C-Mill gait adaptability training can help to improve gait adjustments and associated attentional demands. Sixteen community-ambulating persons in the chronic stage of stroke (age: 54.8 ± 10.8 years) received ten sessions of C-Mill training within 5–6 weeks. Prior to and after the intervention period, participants performed an obstacle-avoidance task with and without a secondary attention-demanding auditory Stroop task to assess their ability to make gait adjustments (i.e., obstacle-avoidance success rates) as well as the associated attentional demands (i.e., Stroop success rates, stratified for pre-crossing, crossing, and post-crossing strides). Obstacle-avoidance success rates improved after C-Mill training from 52.4 ± 16.3 % at pretest to 77.0 ± 16.4 % at posttest (p < 0.001). This improvement was accompanied by greater Stroop success rates during the obstacle-crossing stride only (pretest: 62.9 ± 24.9 %, posttest: 77.5 ± 20.4 %, p = 0.006). The observed improvements in obstacle-avoidance success rates and Stroop success rates were strongly correlated (r = 0.68, p = 0.015). The ability to make gait adjustments and the associated attentional demands can be successfully targeted in persons with stroke using C-Mill training, which suggests that its underlying assumptions regarding motor control are appropriate. This study lends support and guidance for designing a randomized controlled trial to further examine the potential of C-Mill training for improving safe community ambulation after stroke.