Many species in Rosaceae, Solanaceae, and Plantaginaceae exhibit S-RNase-based self-incompatibility (SI). In this system, the pistil and pollen specificities are determined by S-RNase and the S locus F-box protein, respectively. The pollen S determinant F-box protein in Prunus (Rosaceae) is referred to by two different terms, SFB (for S-haplotype-specific F-box protein) and SLF (for S locus F box), whereas it is called SLF in Solanaceae and Plantaginaceae. Prunus SFB is thought to be a molecule indispensable for its cognate S-RNase to exert cytotoxicity and to arrest pollen tube growth in incompatible reactions. Although recent studies have demonstrated the molecular function of SCFSLF in the SI reaction of Solanaceae and Plantaginaceae, how SFB participates in the Prunus SI mechanism remains to be elucidated. Here we report the identification of sweet cherry (Prunus avium) SFB (PavSFB)-interacting Skp1-like1 (PavSSK1) using a yeast (Saccharomyces cerevisiae) two-hybrid screening against the pollen cDNA library. Phylogenetic analysis showed that PavSSK1 belongs to the same clade as Antirrhinum hispanicum SLF-interacting Skp1-like1 and Petunia hybrida SLF-interacting Skp1-like1 (PhSSK1). In yeast, PavSSK1 interacted not only with PavSFBs from different S haplotypes and Cullin1-likes (PavCul1s), but also with S-locus F-box-likes. A pull-down assay confirmed the interactions between PavSSK1 and PavSFB and between PavSSK1 and PavCul1s. These results collectively indicate that PavSSK1 could be a functional component of the SCF complex and that PavSFB may function as a component of the SCF complex. We discuss the molecular function of PavSFB in self-/nonself-recognition in the gametophytic SI of Prunus.