Male genitalia evolve rapidly, probably as a result of sexual selection. Whether this pattern extends to the internal infrastructure that influences genital movements remains unknown. Cetaceans (whales and dolphins) offer a unique opportunity to test this hypothesis: since evolving from land-dwelling ancestors, they lost external hind limbs and evolved a highly reduced pelvis which seems to serve no other function except to anchor muscles that maneuver the penis. Here we create a novel morphometric pipeline to analyze the size and shape evolution of pelvic bones from 130 individuals (29 species) in the context of inferred mating system. We present two main findings: 1) males from species with relatively intense sexual selection (inferred by relative testes size) have evolved relatively large penises and pelvic bones compared to their body size, and 2) pelvic bone shape diverges more quickly in species pairs that have diverged in inferred mating system. Neither pattern was observed in the anterior-most pair of vertebral ribs, which served as a negative control. This study provides evidence that sexual selection can affect internal anatomy that controls male genitalia. These important functions may explain why cetacean pelvic bones have not been lost through evolutionary time.