The dramatic expansion of the geographical range of coyotes over the last 90 years is partly explained by changes to the landscape and local extinctions of wolves, but hybridization may also have facilitated their movement. We present mtDNA sequence data from 686 eastern coyotes and measurements of 196 skulls related to their two-front colonization pattern. We find evidence for hybridization with Great Lakes wolves only along the northern front, which is correlated with larger skull size, increased sexual dimorphism and a five times faster colonization rate than the southern front. Northeastern haplotype diversity is low, suggesting that this population was founded by very few females moving across the Saint Lawrence River. This northern front then spread south and west, eventually coming in contact with an expanding front of non-hybrid coyotes in western New York and Pennsylvania. We suggest that hybridization with wolves in Canada introduced adaptive variation that contributed to larger size, which in turn allowed eastern coyotes to better hunt deer, allowing a more rapid colonization of new areas than coyotes without introgressed wolf genes. Thus, hybridization is a conduit by which genetic variation from an extirpated species has been reintroduced into northeastern USA, enabling northeastern coyotes to occupy a portion of the niche left vacant by wolves.