The Cumanians were originally Asian pastoral nomads who in the 13th century migrated to Hungary. We have examined mitochondrial DNA from members of the earliest Cumanian population in Hungary from two archeologically well-documented excavations and from 74 modern Hungarians from different rural locations in Hungary. Haplogroups were defined based on HVS I sequences and examinations of haplogroup-associated polymorphic sites of the protein coding region and of HVS II. To exclude contamination, some ancient DNA samples were cloned. A database was created from previously published mtDNA HVS I sequences (representing 2,615 individuals from different Asian and European populations) and 74 modem Hungarian sequences from the present study. This database was used to determine the relationships between the ancient Cumanians, modern Hungarians, and Eurasian populations and to estimate the genetic distances between these populations. We attempted to deduce the genetic trace of the migration of Cumanians. This study is the first ancient DNA characterization of an eastern pastoral nomad population that migrated into Europe. The results indicate that, while still possessing a Central Asian steppe culture, the Cumanians received a large admixture of maternal genes from more westerly populations before arriving in Hungary. A similar dilution of genetic, but not cultural, factors may have accompanied the settlement of other Asian nomads in Europe.