The mantis genus Tenodera is composed of several species distributed across Africa, Asia and Australasia, along with recent human introductions to North America. Species of the genus are morphologically similar and utilise equivalent habitats across their distribution. Relationships among these species and the morphological characters used to diagnose them have never been formally tested, leaving authors to disagree as to the species composition of Tenodera. With DNA sequence data from five molecular loci and morphological characters from male genitalia, we reconstructed the phylogeny of Tenodera using multiple optimality criteria. All included species were found to be monophyletic in analyses of the combined data. Tenodera sinensis and T. bokiana were both supported as distinct species recovered in separate clades, resolving confusion as to their placement and classification. Our analysis identified a previously undescribed species of Tenodera collected in India, recovered as sister to T. aridifolia and T. sinensis, and exhibiting distinct male genital morphology. In light of the phylogeny, we characterise for the first time, and investigate the evolution of, the male genitalia, which allowed us to discover several transitions in structural forms. We also consider the connection of these transitions to sexual cannibalism and how this behaviour may have led to rapid evolution of the male genitalia.