Higher plants produce seed through pollination, using specific interactions between pollen and pistil. Self-incompatibility is an important mechanism used in many species to prevent inbreeding; it is controlled by a multi-allelic S locus. 'Self' (incompatible) pollen is discriminated from 'non-self' (compatible) pollen by interaction of pollen and pistil S locus components, and is subsequently inhibited. In Papaver rhoeas, the pistil S locus product is a small protein that interacts with incompatible pollen, triggering a Ca(2+)-dependent signalling network, resulting in pollen inhibition and programmed cell death. Here we have cloned three alleles of a highly polymorphic pollen-expressed gene, PrpS (Papaver rhoeas pollen S), from Papaver and provide evidence that this encodes the pollen S locus determinant. PrpS is a single-copy gene linked to the pistil S gene (currently called S, but referred to hereafter as PrsS for Papaver rhoeas stigma S determinant). Sequence analysis indicates that PrsS and PrpS are equally ancient and probably co-evolved. PrpS encodes a novel approximately 20-kDa protein. Consistent with predictions that it is a transmembrane protein, PrpS is associated with the plasma membrane. We show that a predicted extracellular loop segment of PrpS interacts with PrsS and, using PrpS antisense oligonucleotides, we demonstrate that PrpS is involved in S-specific inhibition of incompatible pollen. Identification of PrpS represents a major advance in our understanding of the Papaver self-incompatibility system. As a novel cell-cell recognition determinant it contributes to the available information concerning the origins and evolution of cell-cell recognition systems involved in discrimination between self and non-self, which also include histocompatibility systems in primitive chordates and vertebrates.