In Petunia (Solanaceae family), self-incompatibility (SI) is regulated by the polymorphic S-locus, which contains the pistil-specific S-RNase and multiple pollen-specific S-Locus F-box (SLF) genes. SLFs assemble into E3 ubiquitin ligase complexes known as Skp1-Cullin1-F-box complexes (SCFSLF). In pollen tubes, these complexes collectively mediate ubiquitination and degradation of all nonself S-RNases, but not self S-RNase, resulting in cross-compatible, but self-incompatible, pollination. Using Petunia inflata, we show that two pollen-expressed Cullin1 (CUL1) proteins, PiCUL1-P and PiCUL1-B, function redundantly in SI. This redundancy is lost in Petunia hybrida, not because of the inability of PhCUL1-B to interact with SSK1, but due to a reduction in the PhCUL1-B transcript level. This is possibly caused by the presence of a DNA transposon in the PhCUL1-B promoter region, which was inherited from Petunia axillaris, one of the parental species of Pe. hybrida. Phylogenetic and syntenic analyses of Cullin genes in various eudicots show that three Solanaceae-specific CUL1 genes share a common origin, with CUL1-P dedicated to S-RNase-related reproductive processes. However, CUL1-B is a dispersed duplicate of CUL1-P present only in Petunia, and not in the other species of the Solanaceae family examined. We suggest that the CUL1s involved (or potentially involved) in the SI response in eudicots share a common origin.