Grylloblattids (ice crawlers) inhabit montane talus slopes and ice caves in North America and Asia. Grylloblatta campodeiformis consists of a large number of known populations scattered across a large geographical region, while other described species are restricted to a more narrow distributional range. Since grylloblattids are restricted to cold environments, migration is probably very rare, and one might expect their phylogenetic and population structure to reflect the placement of ice sheets and glacial refugia during the Pleistocene. We sequenced mitochondrial and nuclear markers from 20 Grylloblatta (North America) populations, three Galloisiana (Japan) populations, and three Grylloblattina (Russia) populations. Phylogenetic and population genetic analysis of these data suggest that the genus Grylloblatta is monophyletic, that each population is reciprocally monophyletic, and that their population structure is correlated with geography. Population structure relative to Pleistocene glaciation will be discussed.