S-RNase-based self-incompatibility (SI) is an intraspecific reproductive barrier to prevent self-fertilization found in many species of the Solanaceae, Plantaginaceae and Rosaceae. In this system, S-RNase and SLF/SFB (S-locus F-box) genes have been shown to control the pistil and pollen SI specificity, respectively. Recent studies have shown that the SLF functions as a substrate receptor of a SCF (Skp1/Cullin1/F-box)-type E3 ubiquitin ligase complex to target S-RNases in Solanaceae and Plantaginaceae, but its role in Rosaceae remains largely undefined. Here we report the identification of two pollen-specific SLF-interacting Skp1-like (SSK) proteins, PbSSK1 and PbSSK2, in Pyrus bretschneideri from the tribe Pyreae of Rosaceae. Both yeast two-hybrid and pull-down assays demonstrated that they could connect PbSLFs to PbCUL1 to form a putative canonical SCF(SLF) (SSK/CUL1/SLF) complex in Pyrus. Furthermore, pull-down assays showed that the SSK proteins could bind SLF and CUL1 in a cross-species manner between Pyrus and Petunia. Additionally, phylogenetic analysis revealed that the SSK-like proteins from Solanaceae, Plantaginaceae and Rosaceae form a monoclade group, hinting their shared evolutionary origin. Taken together, with the recent identification of a canonical SCF(SFB) complex in Prunus of the tribe Amygdaleae of Rosaceae, our results show that a conserved canonical SCF(SLF/SFB) complex is present in Solanaceae, Plantaginaceae and Rosaceae, implying that S-RNase-based self-incompatibility shares a similar molecular and biochemical mechanism.