Rabies spreads in both Arctic (Vulpes lagopus) and red foxes (Vulpes vulpes) throughout the Canadian Arctic but limited wildlife disease surveillance, due to the extensive landmass of the Canadian north and its small widely scattered human population, undermines our knowledge of disease transmission patterns. This study has explored genetic population structure in both the rabies virus and its fox hosts to better understand factors that impact rabies spread. Phylogenetic analysis of 278 samples of the Arctic lineage of rabies virus recovered over 40 years identified four sub-lineages, A1 to A4. The A1 lineage has been restricted to southern regions of the Canadian province of Ontario. The A2 lineage, which predominates in Siberia, has also spread to northern Alaska while the A4 lineage was recovered from southern Alaska only. The A3 sub-lineage, which was also found in northern Alaska, has been responsible for virtually all cases across northern Canada and Greenland, where it further differentiated into 18 groups which have systematically evolved from a common predecessor since 1975. In areas of Arctic and red fox sympatry, viral groups appear to circulate in both hosts, but both mitochondrial DNA control region sequences and 9-locus microsatellite genotypes revealed contrasting phylogeographic patterns for the two fox species. Among 157 Arctic foxes, 33 mitochondrial control region haplotypes were identified but little genetic structure differentiating localities was detected. Among 162 red foxes, 18 control region haplotypes delineated three groups which discriminated among the Churchill region of Manitoba, northern Quebec and Labrador populations, and the coastal Labrador locality of Cartwright. Microsatellite analyses demonstrated some genetic heterogeneity among sampling localities of Arctic foxes but no obvious pattern, while two or three clusters of red foxes suggested some admixture between the Churchill and Quebec-Labrador regions but uniqueness of the Cartwright group. The limited population structure of Arctic foxes is consistent with the rapid spread of rabies virus subtypes throughout the north, while red fox population substructure suggests that disease spread in this host moves most readily down certain independent corridors such as the northeastern coast of Canada and the central interior. Interestingly the evidence suggests that these red fox populations have limited capacity to maintain the virus over the long term, but they may contribute to viral persistence in areas of red and Arctic fox sympatry.