Here, we present a study regarding the phylogenetic positions of two enigmatic earwig lineages whose unique phenotypic traits evolved in connection with ectoparasitic relationships with mammals. Extant earwigs (Dermaptera) have traditionally been divided into three suborders: the Hemimerina, Arixeniina, and Forficulina. While the Forficulina are typical, well-known, free-living earwigs, the Hemimerina and Arixeniina are unusual epizoic groups living on molossid bats (Arixeniina) or murid rodents (Hemimerina). The monophyly of both epizoic lineages is well established, but their relationship to the remainder of the Dermaptera is controversial because of their extremely modified morphology with paedomorphic features. We present phylogenetic analyses that include molecular data (18S and 28S ribosomal DNA and histone-3) for both Arixeniina and Hemimerina for the first time. This data set enabled us to apply a rigorous cladistics approach and to test competing hypotheses that were previously scattered in the literature. Our results demonstrate that Arixeniidae and Hemimeridae belong in the dermapteran suborder Neodermaptera, infraorder Epidermaptera, and superfamily Forficuloidea. The results support the sister group relationships of Arixeniidae+Chelisochidae and Hemimeridae+Forficulidae. This study demonstrates the potential for rapid and substantial macroevolutionary changes at the morphological level as related to adaptive evolution, in this case linked to the utilization of a novel trophic niche based on an epizoic life strategy. Our results also indicate that the evolutionary consequences of the transition to an ectoparazitic mode of living, which is extremely rare in earwigs, have biased previous morphology-based hypotheses regarding the phylogeny of this insect group.