The fossil record of mammaliaforms (mammals and their closest relatives) of the Mesozoic era from the southern supercontinent Gondwana is far less extensive than that from its northern counterpart, Laurasia1,2. Among Mesozoic mammaliaforms, Gondwanatheria is one of the most poorly known clades, previously represented by only a single cranium and isolated jaws and teeth1-5. As a result, the anatomy, palaeobiology and phylogenetic relationships of gondwanatherians remain unclear. Here we report the discovery of an articulated and very well-preserved skeleton of a gondwanatherian of the latest age (72.1-66 million years ago) of the Cretaceous period from Madagascar that we assign to a new genus and species, Adalatherium hui. To our knowledge, the specimen is the most complete skeleton of a Gondwanan Mesozoic mammaliaform that has been found, and includes the only postcranial material and ascending ramus of the dentary known for any gondwanatherian. A phylogenetic analysis including the new taxon recovers Gondwanatheria as the sister group to Multituberculata. The skeleton, which represents one of the largest of the Gondwanan Mesozoic mammaliaforms, is particularly notable for exhibiting many unique features in combination with features that are convergent on those of therian mammals. This uniqueness is consistent with a lineage history for A. hui of isolation on Madagascar for more than 20 million years.