Most birds have simple genitalia; males lack external genitalia and females have simple vaginas. However, male waterfowl have a phallus whose length (1.5->40 cm) and morphological elaborations vary among species and are positively correlated with the frequency of forced extra-pair copulations among waterfowl species. Here we report morphological complexity in female genital morphology in waterfowl and describe variation vaginal morphology that is unprecedented in birds. This variation comprises two anatomical novelties: (i) dead end sacs, and (ii) clockwise coils. These vaginal structures appear to function to exclude the intromission of the counter-clockwise spiralling male phallus without female cooperation. A phylogenetically controlled comparative analysis of 16 waterfowl species shows that the degree of vaginal elaboration is positively correlated with phallus length, demonstrating that female morphological complexity has co-evolved with male phallus length. Intersexual selection is most likely responsible for the observed coevolution, although identifying the specific mechanism is difficult. Our results suggest that females have evolved a cryptic anatomical mechanism of choice in response to forced extra-pair copulations.