Tetraploid sour cherry (Prunus cerasus L.) exhibits gametophytic self-incompatibility (GSI) whereby the specificity of self-pollen rejection is controlled by alleles of the stylar and pollen specificity genes, S-RNase and SFB (S haplotype-specific F-box protein gene), respectively. As sour cherry selections can be either self-compatible (SC) or self-incompatible (SI), polyploidy per se does not result in SC. Instead the genotype-dependent loss of SI in sour cherry is due to the accumulation of non-functional S-haplotypes. The presence of two or more non-functional S-haplotypes within sour cherry 2x pollen renders that pollen SC. Two new S-haplotypes from sour cherry, S33 and S34, that are presumed to be contributed by the P. fruticosa species parent, the complete S-RNase and SFB sequences of a third S-haplotype, S35, plus the presence of two previously identified sweet cherry S-haplotypes, S14 and S16 are described here. Genetic segregation data demonstrated that the S16-, S33-, S34-, and S35-haplotypes present in sour cherry are fully functional. This result is consistent with our previous finding that ‘hetero-allelic’ pollen is incompatible in sour cherry. Phylogenetic analyses of the SFB and S-RNase sequences from available Prunus species reveal that the relationships among S-haplotypes show no correspondence to known organismal relationships at any taxonomic level within Prunus, indicating that polymorphisms at the S-locus have been maintained throughout the evolution of the genus. Furthermore, the phylogenetic relationships among SFB sequences are generally incongruent with those among S-RNase sequences for the same S-haplotypes. Hypotheses compatible with these results are discussed.