The Paleo-Eskimo Saqqaq and Independence I cultures, documented from archaeological remains in Northern Canada and Greenland, represent the earliest human expansion into the New World's northern extremes. However, their origin and genetic relationship to later cultures are unknown. We sequenced a mitochondrial genome from a Paleo-Eskimo human by using 3400-to 4500-year-old frozen hair excavated from an early Greenlandic Saqqaq settlement. The sample is distinct from modern Native Americans and Neo-Eskimos, falling within haplogroup D2a1, a group previously observed among modern Aleuts and Siberian Sireniki Yuit. This result suggests that the earliest migrants into the New World's northern extremes derived from populations in the Bering Sea area and were not directly related to Native Americans or the later Neo-Eskimos that replaced them.