Assortative mating, a potentially efficient prezygotic reproductive barrier, may prevent loss of genetic potential by avoiding the production of unfit hybrids (i.e., because of hybrid infertility or hybrid breakdown) that occur at regions of secondary contact between incipient species. In the case of the mouse hybrid zone, where two subspecies of Mus musculus (M. m. domesticus and M. m. musculus) meet and exchange genes to a limited extent, assortative mating requires a means of subspecies recognition. We based the work reported here on the hypothesis that, if there is a pheromone sufficiently diverged between M. m. domesticus and M. m. musculus to mediate subspecies recognition, then that process must also require a specific receptor(s), also sufficiently diverged between the subspecies, to receive the signal and elicit an assortative mating response. We studied the mouse V1R genes, which encode a large family of receptors in the vomeronasal organ (VNO), by screening Perlegen SNP data and identified one, Vmn1r67, with 24 fixed SNP differences most of which (15/24) are nonsynonymous nucleotide substitutions between M. m. domesticus and M. m. musculus. We observed substantial linkage disequilibrium (LD) between Vmn1r67 and Abpa27, a mouse salivary androgen-binding protein gene that encodes a proteinaceous pheromone (ABP) capable of mediating assortative mating, perhaps in conjunction with its bound small lipophilic ligand. The LD we observed is likely a case of association rather than residual physical linkage from a very recent selective sweep, because an intervening gene, Vmn1r71, shows significant intra(sub)specific polymorphism but no inter(sub)specific divergence in its nucleotide sequence. We discuss alternative explanations of these observations, for example that Abpa27 and Vmn1r67 are coevolving as signal and receptor to reinforce subspecies hybridization barriers or that the unusually divergent Vmn1r67 allele was not a product of fast positive selection, but was derived from an introgressed allele, possibly from Mus spretus.