Squash was first domesticated in Mexico and is now found throughout North America (NA) along with Peponapis pruinosa, a pollen specialist bee species of the squash genus Cucurbita. The origin and spread of squash cultivation is well-studied archaeologically and phylogenetically; however, no study has documented how cultivation of this or any other crop has influenced species in mutualistic interactions. We used molecular markers to reconstruct the demographic range expansion and colonization routes of P. pruinosa from its native range into temperate NA. Populations east of the Rocky Mountains expanded from the wild host plant's range in Mexico and were established by a series of founder events. Eastern North America was most likely colonized from squash bee populations in the present-day continental Midwest USA and not from routes that followed the Gulf and Atlantic coasts from Mexico. Populations of P. pruinosa west of the Rockies spread north from the warm deserts much more recently, showing two genetically differentiated populations with no admixture: one in California and the other one in eastern Great Basin. These bees have repeatedly endured severe bottlenecks as they colonized NA, following human spread of their Cucurbita pollen hosts during the Holocene.