Background and Purpose: The main objective of this randomized trial was to determine whether treadmill walking with body weight support was effective at establishing independent walking more often and earlier than current physiotherapy intervention for nonambulatory stroke patients. Methods: A randomized trial with concealed allocation, blinded assessment, and intention-to-treat analysis was conducted. One hundred twenty-six stroke patients who were unable to walk were recruited and randomly allocated to an experimental or a control group within 4 weeks of stroke. The experimental group undertook up to 30 minutes per day of treadmill walking with body weight support via an overhead harness whereas the control group undertook up to 30 minutes of overground walking. The primary outcome was the proportion of participants achieving independent walking within 6 months. Results: Kaplan–Meier estimates of the proportion of experimental participants who achieved independent walking were 37% compared with 26% of the control group at 1 month, 66% compared with 55% at 2 months, and 71% compared with 60% at 6 months (P=0.13). The experimental group walked 2 weeks earlier, with a median time to independent walking of 5 weeks compared to 7 weeks for the control group. In addition, 14% (95% CI, -1–28) more of the experimental group were discharged home. Conclusions: Treadmill walking with body weight support is feasible, safe, and tends to result in more people walking independently and earlier after stroke.