Ice crawlers (Insecta: Grylloblattodea) are rarely encountered insects that consist of five genera representing 26 species from North America and Asia. Asian grylloblattids are the most diverse, but North American ice crawlers (genus Grylloblatta) are known for their adaptation to cold conditions. Phylogenetic relationships among grylloblattid species and genera are not known. Six genes were sampled in 35 individuals for 18S rRNA, 28S rRNA, histone 3, 12S rRNA, 16S rRNA, and cytochrome oxidase II from 21 populations of Grylloblatta, three populations from Japan (genus Galloisiana), and three populations from Russia (genus Grylloblattina). Phylogenetic analysis of these data with two mantophasmid outgroups in POY supported monophyletic genera, with Grylloblatta as sister to Grylloblattina. Grylloblatta was shown to contain two major lineages: a clade in Northern California and Oregon and a clade in Washington and Oregon. One new species and six candidate species are proposed. IUCN Red List Conservation Criteria were implemented to designate conservation status for each lineage.