Male genitals are highly divergent in animals with internal fertilization. Most studies attempting to explain this diversity have focussed on testing the major hypotheses of genital evolution (the lock-and-key, pleiotropy and sexual selection hypotheses) and quantifying the form of selection targeting male genitals has played an important role in this endeavour. However, we currently know far less about selection targeting female genitals or how male and female genitals interact during mating. Here we use formal selection analysis to show that genital size and shape is subject to strong multivariate stabilizing sexual selection in both sexes of the red flour beetle, Tribolium castaneum. Moreover, we show significant sexual selection on the covariance between the sexes for specific aspects of genital shape suggesting that male and female genitalia also interact to determine the successful transfer of a spermatophore during mating. Our work therefore highlights the important role that both male and female genital morphology plays in determining mating success and that these effects can occur independently, as well as through their interaction. Moreover, it cautions against the overly-simplistic view that the sexual selection targeting genital morphology will always be directional in form and restricted primarily to males.