Glyptodonts were giant (some of them up to ~2400 kg), heavily armoured relatives of living armadillos, which became extinct during the Late Pleistocene/early Holocene alongside much of the South American megafauna. Although glyptodonts were an important component of Cenozoic South American faunas, their early evolution and phylogenetic affinities within the order Cingulata (armoured New World placental mammals) remain controversial. In this study, we used hybridization enrichment and high-throughput sequencing to obtain a partial mitochondrial genome from Doedicurus sp., the largest (1.5 m tall, and 4 m long) and one of the last surviving glyptodonts. Our molecular phylogenetic analyses revealed that glyptodonts fall within the diversity of living armadillos. Reanalysis of morphological data using a molecular ‘backbone constraint’ revealed several morphological characters that supported a close relationship between glyptodonts and the tiny extant fairy armadillos (Chlamyphorinae). This is surprising as these taxa are among the most derived cingulates: glyptodonts were generally large-bodied and heavily armoured, while the fairy armadillos are tiny (~9–17 cm) and adapted for burrowing. Calibration of our phylogeny with the first appearance of glyptodonts in the Eocene resulted in a more precise timeline for xenarthran evolution. The osteological novelties of glyptodonts and their specialization for grazing appear to have evolved rapidly during the Late Eocene to Early Miocene, coincident with global temperature decreases and a shift from wet closed forest towards drier open woodland and grassland across much of South America. This environmental change may have driven the evolution of glyptodonts, culminating in the bizarre giant forms of the Pleistocene.