Human walking involves coordinated movements of all four limbs. The benefits of incorporating arm movements in gait rehabilitation are not known and difficult to investigate in patient populations with poor balance and reduced walking capacity. This study assessed the effect of supported (SUP) versus unsupported (UNSUP) arm movements on the coordination patterns present during walking in individuals with and without a stroke. Ten high functioning stroke subjects and 10 healthy subjects walked on a treadmill while swinging their arms naturally, and while holding onto handles that were either fixed in place or allowed to slide along horizontal handrails. Full-body kinematics were recorded, and arm-leg coordination was quantified using relative phase index, mean relative phase, and cross-correlation of hip and shoulder angle time series. No differences were observed in any measures of coordination between healthy and stroke subjects, indicating that the ability to coordinate arm and leg movements during walking remains preserved in high functioning stroke individuals. Coordination patterns were also unaffected by the use of sliding handrails, suggesting that this paradigm may be a suitable surrogate for natural arm movements if individuals are unable to walk without an external support. Stroke subjects were able to perform arm movements at a faster walking speed when using the handles than they were able to achieve without the handles, indicating that this paradigm may be useful in encouraging arm movements during gait rehabilitation.