Disentangling the origin of putatively introduced/invasive species is of increasing priority in conservation biology. The presence of a previously undocumented species may be due to an undetected recent population or range expansion associated with environmental change, or due to an introduction by humans. We used molecular tools to address the origin of a population of threespine stickleback (Gasterosteus aculeatus) first identified in central Alberta, Canada in 1980 from a single lake. We characterized this inland, high elevation Alberta population in comparison to samples from five representative geographic regions worldwide, using mtDNA and nine microsatellite loci to elucidate genetic structure and estimate divergence times. We found significantly lower levels of genetic variation in the Alberta population, which could reflect either a recent colonization or periodic bottlenecks associated with winterkills. While we did find that the Alberta samples were most closely related to the North American West Coast populations, we did not uncover a putative source population. Alberta samples formed a clade in phylogenetic analyses, with divergence time estimates between the Alberta and British Columbia samples ca. 250–750 kya. The hypothesis that the Alberta population represents a natural colonization during North America’s last glacial recession could not be rejected. Collectively, these data suggest that the genetic signature of colonizing populations following introductions may be similar to populations at their range limit, contributing to difficulties establishing population origins.