Human gait is symmetric and bilaterally coordinated in young healthy persons. In this study, we aimed to explore the differences in bilateral coordination of gait as measured by the phase coordination index (PCI), gait asymmetry, and stride time variability of gait between four age groups. A total of 44 older adults were recruited: nine young-old (age 70–74 years), 26 old (age 75–84 years), nine old-old (>85 years and older), and 13 young adults (age 20–30 years). Subjects walked on a treadmill; walking speed was systematically increased from 0.5 to 0.9 m/s in steps of 0.1 m/s. There were marginal effects of age on PCI, significant main effects of walking speeds without interaction between walking speeds and age group. A difference in PCI could distinguish between young’s and late aging group, and only during their preferred treadmills walking speed. This study explicitly shows that bilateral coordination of walking is modified by gait speed, and deteriorates only at a very old age.