The generation of reproductive incompatibility between groups requires a rare genotype with low compatibility to increase in frequency. We tested the hypothesis that sexual conflict driven by the risk of polyspermy can generate compatibility groups in gamete recognition proteins (GRPs) in the sea urchin Mesocentrotus franciscanus. We examined variation in the sperm (bindin) and egg (EBR1) GRPs, how this variation influences fertilization success and how allele frequencies shift in these GRPs over time. The EBR1 gene is a large, 4595 amino acid, protein made up of 27 TSP and 20 CUB repeats. Two TSP and two CUB repeats each demonstrate two common non-synonymous haplotypes (alleles). Sperm bindin and one of these EBR1 repeats (TSP8) shift allele frequencies from one common to two common types over an approximate 200 year interval associated with the removal of predatory sea otters and rising sea urchin abundances; the egg receptor shifts first, followed by the sperm ligand. Laboratory crosses indicate that the historically common sperm and egg gamete recognition proteins have high compatibility as do the new common proteins, with mismatches having lower compatibility. This process of creating compatibility groups sets the stage for reproductive isolation and speciation.