Background: It is widely accepted that the ancestors of Native Americans arrived in the New World via Beringia approximately 10 to 30 thousand years ago (kya). However, the arrival time(s), number of expansion events, and migration routes into the Western Hemisphere remain controversial because linguistic, archaeological, and genetic evidence have not yet provided coherent answers. Notably, most of the genetic evidence has been acquired from the analysis of the common pan-American mitochondrial DNA (mtDNA) haplogroups. In this study, we have instead identified and analyzed mtDNAs belonging to two rare Native American haplogroups named D4h3 and X2a. Results: Phylogeographic analyses at the highest level of molecular resolution (69 entire mitochondrial genomes) reveal that two almost concomitant paths of migration from Beringia led to the Paleo-Indian dispersal approximately 15-17 kya. Haplogroup D4h3 spread into the Americas along the Pacific coast, whereas X2a entered through the ice-free corridor between the Laurentide and Cordilleran ice sheets. The examination of an additional 276 entire mtDNA sequences provides similar entry times for all common Native American haplogroups, thus indicating at least a dual origin for Paleo-Indians. Conclusions: A dual origin for the first Americans is a striking novelty from the genetic point of view, and it makes plausible a scenario positing that within a rather short period of time, there may have been several entries into the Americas from a dynamically changing Beringian source. Moreover, this implies that most probably more than one language family was carried along with the Paleo-Indians.