No large group of recently extinct placental mammals remains as evolutionarily cryptic as the approximately 280 genera grouped as ‘South American native ungulates’. To Charles Darwin, who first collected their remains, they included perhaps the ‘strangest animal[s] ever discovered’. Today, much like 180 years ago, it is no clearer whether they had one origin or several, arose before or after the Cretaceous/Palaeogene transition 66.2 million years ago, or are more likely to belong with the elephants and sirenians of superorder Afrotheria than with the euungulates (cattle, horses, and allies) of superorder Laurasiatheria. Morphology-based analyses have proved unconvincing because convergences are pervasive among unrelated ungulate-like placentals. Approaches using ancient DNA have also been unsuccessful, probably because of rapid DNA degradation in semitropical and temperate deposits. Here we apply proteomic analysis to screen bone samples of the Late Quaternary South American native ungulate taxa Toxodon (Notoungulata) and Macrauchenia (Litopterna) for phylogenetically informative protein sequences. For each ungulate, we obtain approximately 90% direct sequence coverage of type I collagen α1- and α2-chains, representing approximately 900 of 1,140 amino-acid residues for each subunit. A phylogeny is estimated from an alignment of these fossil sequences with collagen (I) gene transcripts from available mammalian genomes or mass spectrometrically derived sequence data obtained for this study. The resulting consensus tree agrees well with recent higher-level mammalian phylogenies. Toxodon and Macrauchenia form a monophyletic group whose sister taxon is not Afrotheria or any of its constituent clades as recently claimed, but instead crown Perissodactyla (horses, tapirs, and rhinoceroses). These results are consistent with the origin of at least some South American native ungulates from ‘condylarths’, a paraphyletic assembly of archaic placentals. With ongoing improvements in instrumentation and analytical procedures, proteomics may produce a revolution in systematics such as that achieved by genomics, but with the possibility of reaching much further back in time.