During the Pleistocene pygmy elephantids, some only a quarter of their ancestors' size, were present on Mediterranean islands until about 10 000 years ago (y.a.). Using a new methodology for ancient DNA (aDNA) studies, the whole genomic multiple displacement amplification method, we were able to retrieve cytochrome b (cytb) DNA fragments from 4200 to 800 000 y.a. specimens from island and mainland samples, including pygmy and normal-sized forms. The short DNA sequence (43 bp) retrieved from the 800 000 y.a. sample is one of the oldest DNA fragment ever retrieved. Duplication of the experiments in two laboratories, the occurrence of three diagnostic sites and the results of the phylogenetic analyses strongly support its authenticity. Our results challenge the prevailing view that pygmy elephantids of the eastern Mediterranean originated exclusively from Elephas, suggesting independent histories of dwarfism and the presence of both pygmy mammoths and elephant-like taxa on these islands. Based on our molecular data, the origin of the Tilos and Cyprus elephantids from a lineage within the genus Elephas is confirmed, while the DNA sequence from the Cretan sample falls clearly within the mammoth clade. Thus, the name Mammuthus creticus rather than Elephas creticus, seems to be justified for this form. Our findings also suggest a need to re-evaluate the evolutionary history of the Sicilian/Maltese species, traditionally included in the genus Elephas.