The red wolf (Canis rufus) of the eastern US was driven to near-extinction by colonial-era persecution and habitat conversion, which facilitated coyote (C. latrans) range expansion and widespread hybridization with red wolves. The observation of some grey wolf (C. lupus) ancestry within red wolves sparked controversy over whether it was historically a subspecies of grey wolf with its predominant "coyote-like" ancestry obtained from post-colonial coyote hybridization (2-species hypothesis) versus a distinct species closely related to the coyote that hybridized with grey wolf (3-species hypothesis). We analysed mitogenomes sourced from before the 20th century bottleneck and coyote invasion, along with hundreds of modern amplicons, which led us to reject the 2-species model and to investigate a broader phylogeographic 3-species model suggested by the fossil record. Our findings broadly support this model, in which red wolves ranged the width of the American continent prior to arrival of the grey wolf to the mid-continent 60-80 ka; red wolves subsequently disappeared from the mid-continent, relegated to California and the eastern forests, which ushered in emergence of the coyote in their place (50-30 ka); by the early Holocene (12-10 ka), coyotes had expanded into California, where they admixed with and phenotypically replaced western red wolves in a process analogous to the 20th century coyote invasion of the eastern forests. Findings indicate that the red wolf pre-dated not only European colonization but human, and possibly coyote, presence in North America. These findings highlight the urgency of expanding conservation efforts for the red wolf.