Basal neurons of the vomeronasal organ of the mouse express a superfamily of about 120 pheromone receptors, named V2Rs, that are grouped in four families, A, B, C, and D, according to sequence homology. Family-A, -B, and -D V2Rs are expressed as one receptor gene per cell, but we previously reported their co-expression with family-C V2Rs. Here, we show that basal neurons can be further grouped according to the combinatorial expression of different V2Rs. Altogether, these findings suggest that in each basal neuron a transcriptional program is active for expressing a combination of two compatible receptors and for excluding, at the same time, the expression of all other V2Rs. Further analyses revealed non-random combinations of co-expression between family-C V2Rs and genes of the class Ib major histocompatibility complex. Thus, each basal neuron of the vomeronasal organ represents a highly qualified sensory unit for detecting very specific combinations of pheromonal cues.