Vertebrates employ an impressive range of strategies for coordinating their limb movements while walking. Although this gait variation has been quantified and hypotheses for its origins tested in select tetrapod lineages, a comprehensive understanding of gait evolution in a macroevolutionary context is currently lacking. We used freely-available internet videos to nearly double the number of species with quantitative gait data and used phylogenetic comparative methods to test key hypotheses about gait origin and evolution. We find strong support for an ancestral Lateral-Sequence Diagonal-Couplet gait in gnathostomes, and this mode is remarkably conserved throughout tetrapod phylogeny. Evolutionary rate analyses show that mammals overcame this ancestral constraint, resulting in a greater range of gait values than any other tetrapod lineage. Diagonal-Sequence Diagonal-Couplet gaits are significantly associated with arboreality in mammals, though this relationship is not recovered for other tetrapod lineages. Notably, the Lateral-Sequence Lateral-Couplet gait, unique to mammals among extant tetrapods, is not associated with any traditional explanations. The complex drivers of gait diversification in mammals remain unclear, but our analyses suggest that their success was due, in part, to released from a locomotor constraint that has likely persisted in other extant tetrapod lineages for over 375 million years.