Cryptocercus are subsocial, xylophagous cockroaches that live in temperate forests. Like other cockroaches, Cryptocercus harbour endosymbiotic bacteria in their fat bodies. Two species of Cryptocercus occur in the palaearctic, one each in eastern Russia and south-central China. In the USA, there are five species: one in the north-west and four in the south-east. Little is known about the relationship between the Eurasian and North American Cryptocercus or the causes of the disjunct distribution. Here, a molecular phylogeny for six out of the seven Cryptocercus species and their endosymbionts is inferred in an attempt to understand the evolution and biogeography of the genus. Our analysis showed that the North American Cryptocercus are monophyletic, suggesting that a single colonization event was followed by vicariance. There was complete concordance between the host and endosymbiont phylogenetic trees. Divergence estimates based on endosymbiont DNA sequences suggested that the palaearctic and nearctic Cryptocercus diverged 70–115 million years (Myr) ago and the eastern- and western-USA species diverged 53–88 Myr ago. These divergence estimates were correlated with biogeographical events, and a hypothesis is presented to explain the current distribution of Cryptocercus. Our findings suggest that Cryptocercus has had a long evolutionary history, dating back to the Jurassic.