A comprehensive taxonomic and distributional sampling of Mantodea (praying mantises), covering virtually all higher-level groups, was assembled to reconstruct the phylogeny for the order. Sequence data were generated from five mitochondrial and four nuclear loci (12S rDNA, 16S rDNA, 18S rDNA, 28S rDNA, Histone III, Cytochrome Oxidase I & II, NADH dehydrogenase subunit 4, and Wingless) for 329 mantis species along with 15 cockroach and termite species as outgroups. Phylogenetic reconstruction using multiple methods recovered nearly congruent topologies. Only 7 of 14 testable families, 13 of 33 testable subfamilies, and 7 of 14 testable tribes were recovered as monophyletic indicating that phylogeny is largely incongruent with current mantis classification. Mapping biogeographic regions on the phylogeny demonstrated that our results adhere closer to geographic distribution than to the current classification. Specific patterns in distribution suggest that major morphological convergences have confounded taxonomists ability to construct natural groups. Rather, we found that major mantis lineages diverged prior to the isolation of geographic regions and subsequent ecomorphic specializations within these regions led to convergences in morphology. Divergence time estimations place the origins of Mantodea at the beginning of the Jurassic with modern mantises originating on Gondwanaland in the Early Cretaceous. The first major divergence among modern mantises occurred as a result of the splitting of South America from Africa. The subsequent breakup of Gondwanaland continents spurred numerous divergences within the order and led to the contemporary paraphyletic assemblages of taxa within each biogeographic region.