While the monophyly of the order Phasmatodea (stick and leaf insects) and its placement among the remaining insect orders is well supported, many aspects of phasmid phylogeny and evolution remain controversial. Recent morphological and molecular phylogenetic studies all corroborate a Timema + Euphasmatodea (all remaining species) sister grouping, however the basal relationships within Euphasmatodea remain equivocal. Furthermore, current molecular data support a loss of wings at the base of the phasmid clade followed by a long diversification of wingless taxa with wings later recovered independently in multiple lineages throughout phasmid evolution. Approximately 60 morphological characters of the adult form and egg capsule and DNA sequence data (18S rDNA, 28S rDNA, 12S rDNA, 16S rDNA, histone 3, and COII) were obtained for a broad taxonomic sampling within Phasmatodea (~150 taxa). Phylogenetic analyses of these data were performed via Direct Optimization using parsimony and likelihood criteria. The basal diversification of Phasmatodea is investigated to specifically identify the basal most lineage of Euphasmatodea and to test the phasmid loss and recovery of wings hypothesis. These analyses suggest that 1) a clade comprising mostly Diapheromerine taxa form the basal most lineage of Euphasmatodea, 2) the phasmid wing recurrence hypothesis is supported, and 3) there are multiple independent origins of phasmid egg laying strategies. Other taxonomic and biological implications are discussed in light of this phylogeny.