The insular dwarfism seen in Pleistocene elephants has come to epitomize the island rule; yet our understanding of this phenomenon is hampered by poor taxonomy. For Mediterranean dwarf elephants, where the most extreme cases of insular dwarfism are observed, a key systematic question remains unresolved: are all taxa phyletic dwarfs of a single mainland species Palaeoloxodon antiquus (straight-tusked elephant), or are some referable to Mammuthus (mammoths)? Ancient DNA and geochronological evidence have been used to support a Mammuthus origin for the Cretan 'Palaeoloxodon' creticus, but these studies have been shown to be flawed. On the basis of existing collections and recent field discoveries, we present new, morphological evidence for the taxonomic status of 'P'. creticus, and show that it is indeed a mammoth, most probably derived from Early Pleistocene Mammuthus meridionalis or possibly Late Pliocene Mammuthus rumanus. We also show that Mammuthus creticus is smaller than other known insular dwarf mammoths, and is similar in size to the smallest dwarf Palaeoloxodon species from Sicily and Malta, making it the smallest mammoth species known to have existed. These findings indicate that extreme insular dwarfism has evolved to a similar degree independently in two elephant lineages.