The oldest confirmed remains of domestic dogs in North America are from mid-continent archeological sites dated ~9,900 calibrated years before present (cal BP). Although this date suggests that dogs may not have arrived alongside the first Native Americans, the timing and routes for the entrance of New World dogs are unclear. Here, we present a complete mitochondrial genome of a dog from Southeast Alaska, dated to 10,150 ± 260 cal BP. We compared this high-coverage genome with data from modern dog breeds, historical Arctic dogs, and American precontact dogs (PCDs) from before European arrival. Our analyses demonstrate that the ancient dog shared a common ancestor with PCDs that lived ~14,500 years ago and diverged from Siberian dogs around 16,000 years ago, coinciding with the minimum suggested date for the opening of the North Pacific coastal (NPC) route along the Cordilleran Ice Sheet and genetic evidence for the initial peopling of the Americas. This ancient Southeast Alaskan dog occupies an early branching position within the PCD clade, indicating it represents a close relative of the earliest PCDs that were brought alongside people migrating from eastern Beringia southward along the NPC to the rest of the Americas. The stable isotope δ13C value of this early dog indicates a marine diet, different from the younger mid-continent PCDs’ terrestrial diet. Although PCDs were largely replaced by modern European dog breeds, our results indicate that their population decline started ~2,000 years BP, coinciding with the expansion of Inuit peoples, who are associated with traditional sled-dog culture. Our findings suggest that dogs formed part of the initial human habitation of the New World, and provide insights into their replacement by both Arctic and European lineages.