Humans lack the common mammalian cell surface molecule N-glycolylneuraminic acid (Neu5Gc) due to a CMAH gene inactivation, which occurred approximately three million years ago. Modern humans produce antibodies specific for Neu5Gc. We hypothesized that anti-Neu5Gc antibodies could enter the female reproductive tract and target Neu5Gc-positive sperm or fetal tissues, reducing reproductive compatibility. Indeed, female mice with a human-like Cmah(-/-) mutation and immunized to express anti-Neu5Gc antibodies show lower fertility with Neu5Gc-positive males, due to prezygotic incompatibilities. Human anti-Neu5Gc antibodies are also capable of targeting paternally derived antigens and mediate cytotoxicity against Neu5Gc-bearing chimpanzee sperm in vitro. Models of populations polymorphic for such antigens show that reproductive incompatibility by female immunity can drive loss-of-function alleles to fixation from moderate initial frequencies. Initially, the loss of a cell-surface antigen can occur due to drift in isolated populations or when natural selection favors the loss of a receptor exploited by pathogens, subsequently the same loss-of-function allele can come under sexual selection because it avoids being targeted by the female immune system. Thus, we provide evidence of a link between sexual selection and immune function: Antigenicity in females can select against foreign paternal antigens on sperm and rapidly fix loss-of-function alleles. Similar circumstances existed when the CMAH null allele was polymorphic in ancestral hominins, just before the divergence of Homo from australopithecines.