The molecular phylogeny of the Cimicoidea was reconstructed from an expanded sampling based on mitochondrial (16S, COI) and nuclear (18S, 28SD3) genes. The data were analyzed using maximum likelihood (ML), maximum parsimony (MP), and Bayesian inference (BI) phylogenetic frameworks. The phylogenetic relationships inferred by the model-based analyses (ML and BI) were largely congruent with those inferred by the MP analysis in terms of the monophyly of most of the higher taxonomic groups and the species-level relationships. The following clades were recovered in all analyses: Cimiciformes; Nabidae: Prostemmatinae; Nabidae: Nabinae; Plokiophilidae; Microphysidae; Lasiochilidae; Cimicidae: Cacodminae; Cimicidae; Lyctocoridae; Anthocoridae s. str.; Cardiastethini excluding Amphiareus; Almeidini; Scolopini; Anthocorini; Oriini; Curaliidae + Lasiochilidae; Almeidini + Xylocorini; Oriini + Cardiastethini; and Anthocorini + Amphiareus. Reconstructions of ancestral copulation states based on Bayesian and parsimony inference indicated that at least one shift from standard insemination (SI) to traumatic insemination (TI) occurred within Cimicoidea, and an investigation of the evolutionary correlation between TI and paragenitalia (PG) revealed that the acquisition of PG in cimicoid females was correlated with the TI habit. Additionally, our morphological examination of various types of PG suggested that even the same PG type may not constitute a homologous feature at various taxonomic levels, indicating the convergent evolution of female morphology to adapt to TI.