The mantis genus Tenodera consists of several species distributed across Africa, Asia, and Australasia including recent human introductions to North America. Species of the genus are similar morphologically and utilize the same environments across their distribution. However, the relationships among these species and the morphological characters used to delimitate them have never been formally tested. By utilizing molecular data from five loci (12S rDNA, 18S rDNA, 28S rDNA, Histone III, Cytochrome Oxidase II, wingless) and coding morphology characters from male genitalia, we reconstructed phylogenies using multiple optimality criteria. Of the five included species, four were found to be monophyletic and supported as a distinct species. The two subspecies of Tenodera aridifolia, T. aridifolia sinensis and T. aridifolia aridifolia were supported as two distinct species recovered in separate clades supporting the elevation of the subspecies T. a. sinensis to species. Further, our analysis identified a new species of Tenodera collected in India, which falls as sister to T. aridifolia and T. sinensis and exhibits distinct male genitalic morphology. After mapping male genitalic characters onto the phylogeny we see conspicuous transitions in form across the included species. Simpler forms clustered within early branching clades while more complex versions of homologous structures were recovered within more derived species.