The primate foot functions as a grasping organ. As such, its bones, soft tissues, and joints evolved to maximize power and stability in a variety of grasping configurations. Humans are the obvious exception to this primate pattern, with feet that evolved to support the unique biomechanical demands of bipedal locomotion. Of key functional importance to bipedalism is the morphology of the joints at the forefoot, known as the metatarsophalangeal joints (MTPJs), but a comprehensive analysis of hominin MTPJ morphology is currently lacking. Here we present the results of a multivariate shape and Bayesian phylogenetic comparative analyses of metatarsals (MTs) from a broad selection of anthropoid primates (including fossil apes and stem catarrhines) and most of the early hominin pedal fossil record, including the oldest hominin for which good pedal remains exist, Ardipithecus ramidus. Results corroborate the importance of specific bony morphologies such as dorsal MT head expansion and "doming" to the evolution of terrestrial bipedalism in hominins. Further, our evolutionary models reveal that the MT1 of Ar. ramidus shifts away from the reconstructed optimum of our last common ancestor with apes, but not necessarily in the direction of modern humans. However, the lateral rays of Ar. ramidus are transformed in a more human-like direction, suggesting that they were the digits first recruited by hominins into the primary role of terrestrial propulsion. This pattern of evolutionary change is seen consistently throughout the evolution of the foot, highlighting the mosaic nature of pedal evolution and the emergence of a derived, modern hallux relatively late in human evolution.