Mature locomotion requires that animal nervous systems coordinate distinct groups of muscles. The pressures that guide the development of coordination are not well understood. To understand how and why coordination might emerge, we measured the kinematics of spontaneous vertical locomotion across early development in zebrafish (Danio rerio) . We found that zebrafish used their pectoral fins and bodies synergistically during upwards swims. As larvae developed, they changed the way they coordinated fin and body movements, allowing them to climb with increasingly stable postures. This fin-body synergy was absent in vestibular mutants, suggesting sensed imbalance promotes coordinated movements. Similarly, synergies were systematically altered following cerebellar lesions, identifying a neural substrate regulating fin-body coordination. Together these findings link the vestibular sense to the maturation of coordinated locomotion. Developing zebrafish improve postural stability by changing fin-body coordination. We therefore propose that the development of coordinated locomotion is regulated by vestibular sensation.