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 that 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) tend to evolve larger penises and pelvic bones compared to their body length, and (2) pelvic bone shape has diverged more 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.