The living tree sloths Choloepus and Bradypus are the only remaining members of Folivora, a major xenarthran radiation that occupied a wide range of habitats in many parts of the western hemisphere during the Cenozoic, including both continents and the West Indies. Ancient DNA evidence has played only a minor role in folivoran systematics, as most sloths lived in places not conducive to genomic preservation. Here we utilize collagen sequence information, both separately and in combination with published mitochondrial DNA evidence, to assess the relationships of tree sloths and their extinct relatives. Results from phylogenetic analysis of these datasets differ substantially from morphology-based concepts: Choloepus groups with Mylodontidae, not Megalonychidae; Bradypus and Megalonyx pair together as megatherioids, while monophyletic Antillean sloths may be sister to all other folivorans. Divergence estimates are consistent with fossil evidence for mid-Cenozoic presence of sloths in the West Indies and an early Miocene radiation in South America.