Pheromones are chemicals produced and detected by conspecifics to elicit social/sexual physiological and behavioral responses, and they are perceived primarily by the vomeronasal organ (VNO) in terrestrial vertebrates. Two large superfamilies of G protein-coupled receptors, V1rs and V2rs, have been identified as pheromone receptors in vomeronasal sensory neurons. Based on a computational analysis of the mouse and rat genome sequences, we report the first global draft of the V2r gene repertoire, composed of approximately 200 genes and pseudogenes. Rodent V2rs are subject to rapid gene births/deaths and accelerated amino acid substitutions, likely reflecting the species-specific nature of pheromones. Vertebrate V2rs appear to have originated twice prior to the emergence of the VNO in ancestral tetrapods, explaining seemingly inconsistent observations among different V2rs. The identification of the entire V2r repertoire opens the door to genomic-level studies of the structure, function, and evolution of this diverse group of sensory receptors.