Understanding the genetic consequences of changes in species distributions has wide-ranging implications for predicting future outcomes of climate change, for protecting threatened or endangered populations, and for understanding the history that has led to current genetic patterns within species. Herein, we examine the genetic consequences of range expansion over a 25-year period in a parasite (Geomydoecus aurei) that is in the process of expanding its geographic range via invasion of a novel host. By sampling the genetics of 1,935 G. aurei lice taken from 64 host individuals collected over this time period using 12 microsatellite markers, we test hypotheses concerning linear spatial expansion, genetic recovery time, and allele surfing. We find evidence of decreasing allelic richness with increasing distance from the source population, supporting a linear, stepping stone model of spatial expansion that emphasizes the effects of repeated bottleneck events during colonization. We provide evidence of post-bottleneck genetic recovery, with average allelic richness of infrapopulations increasing about 30% over the 225-generation span of time observed directly in this study. Our estimates of recovery rate suggest, however, that recovery has plateaued, and that this population may not reach genetic diversity levels of the source population without further immigration from the source population. Finally, we employ a grid-based sampling scheme in the region of ongoing population expansion and provide empirical evidence for the power of allele surfing to impart genetic structure on a population, even under conditions of selective neutrality and in a place that lacks strong barriers to gene flow.