Phasmatodea comprises over 3,000 extant species and stands out as one of the last remaining insect orders for which a robust, higher-level phylogenetic hypothesis is lacking. New research suggests that the extant diversity is the result of a surprisingly recent and rapid radiation that has been difficult to resolve with standard Sanger sequence data. In order to resolve the early branching events of stick and leaf insects, we analyzed transcriptomes from 61 species, including 38 Phasmatodea species comprising all major clades and 23 outgroup taxa, including all other Polyneoptera orders. Using a custom-made ortholog set based on reference genomes from four species, we identified on average 2,274 orthologous genes in the sequenced transcriptomes. We generated various sub-alignments and performed maximum-likelihood analyses on several representative datasets to evaluate the effect of missing data and matrix composition on our phylogenetic estimates. Based on our new data, we are able to reliably resolve the deeper nodes between the principal lineages of extant Phasmatodea. Among Euphasmatodea, we provide strong evidence for a basal dichotomy of Aschiphasmatodea and all remaining euphasmatodeans, the Neophasmatodea. Within the latter clade, we recovered a previously unrecognized major New World and Old World lineage, for which we introduce the new names Oriophasmata tax. nov. (“Eastern phasmids”) and Occidophasmata tax. nov. (“Western phasmids”). Occidophasmata comprise Diapheromerinae, Pseudophasmatinae, and Agathemera, whereas all remaining lineages form the Oriophasmata, including Heteropterygidae, Phylliinae, Bacillus, Lonchodidae (Necrosciinae + Lonchodinae), Clitumninae, Cladomorphinae, and Lanceocercata. We furthermore performed a divergence time analysis and reconstructed the historical biogeography for stick and leaf insects. Phasmatodea either originated in Southeast Asia or in the New World. Our results suggest that the extant distribution of Phasmatodea is largely the result of dispersal events in a recently and rapidly diversified insect lineage rather than the result of vicariant processes.