Studies on the evolution of reproductive proteins have shown that they tend to evolve more rapidly than other proteins, frequently under positive selection. Progress on understanding the implications of these patterns is possible for marine invertebrates, where molecular evolution can be linked to gamete compatibility. In this study, we surveyed data from the literature from five genera of sea urchins for which there was information on gamete compatibility, divergence of the sperm-egg recognition protein bindin, and mitochondrial divergence. We draw three conclusions: (1) bindin divergence at nonsynonymous sites predicts gamete compatibility, whereas (2) bindin divergence at synonymous sites and mitochondrial DNA divergence do not, and (3) as few as 10 amino acid changes in bindin can lead to complete gamete incompatibility between species. Using mitochondrial divergence as a proxy for time, we find that complete gamete incompatibility can evolve in approximately one and a half million years, whereas sister species can maintain complete gamete compatibility for as long as five million years.