Mitochondrial sequences were retrieved from museum specimens of the enigmatic Andaman Islanders to analyze their evolutionary history. D-loop and protein-coding data reveal that phenotypic similarities with African pygmoid groups are convergent. Genetic and epigenetic data are interpreted as favoring the long-term isolation of the Andamanese, extensive population substructure, and/or two temporally distinct settlements. An early colonization featured populations bearing mtDNA lineage M2, and this lineage is hypothesized to represent the phylogenetic signal of an early southern movement of humans through Asia. The results demonstrate that Victorian anthropological collections can be used to study extinct, or seriously admixed populations, to provide new data about early human origins.