Highly mobile species that thrive in a wide range of habitats are expected to show little genetic differentiation across their range. A limited but growing number of studies have revealed that patterns of broad-scale genetic differentiation can and do emerge in vagile, continuously distributed species. However, these patterns are complex and often shaped by both historical and ecological factors. Comprehensive surveys of genetic variation at a broad scale and at high resolution are useful for detecting cryptic spatial genetic structure, and for investigating the relative roles of historical and ecological processes in structuring widespread, highly mobile species. In this study, we analyzed 10 microsatellite loci from over 1,900 samples collected across the full range of mule deer (Odocoileus hemionus), one of the most widely distributed and abundant of all large mammal species in North America. Through both individual- and population-based analyses we found evidence for three main genetic lineages, one corresponding to the ‘mule deer’ morphological type and two to the ‘black-tailed deer’ type. Historical biogeographic events likely are the primary drivers of genetic divergence in this species; boundaries of the three lineages correspond well with predictions based on Pleistocene glacial cycles and substructure within each lineage demonstrates island vicariance. However, across large geographic areas, including the entire mule deer lineage, we found that genetic variation fit an isolation-by-distance pattern rather than discrete clusters. A lack of genetic structure across wide geographic areas of the continental west indicates that ecological processes have not resulted in restrictions to gene flow sufficient for spatial genetic structure to emerge. Our results have important implications for our understanding of evolutionary mechanisms of divergence, as well as for taxonomy, conservation, and management.