The self-incompatibility (SI) system with the broadest taxonomic distribution in angiosperms is based on multiple S-locus F-box genes (SLFs) tightly linked to an S-RNase termed type-1. Multiple SLFs collaborate to detoxify non-self S-RNases while being unable to detoxify self S-RNases. However, it is unclear how such a system evolved, because in an ancestral system with a single SLF, many non-self S-RNases would not be detoxified, giving low cross-fertilization rates. In addition, how the system has been maintained in the face of whole-genome duplications (WGD) or lost in other lineages remains unclear. Here we show that SLFs from a broad range of species can detoxify S-RNases from Petunia with a high detoxification probability, suggestive of an ancestral feature enabling cross-fertilization and subsequently modified as additional SLFs evolved. We further show, based on its genomic signatures, that type-1 was likely maintained in many lineages, despite WGD, through deletion of duplicate S-loci. In other lineages, SI was lost either through S-locus deletions or by retaining duplications. Two deletion lineages regained SI through type-2 (Brassicaceae) or type-4 (Primulaceae) and one duplication lineage through type-3 (Papaveraceae) mechanisms. Thus, our results reveal a highly dynamic process behind the origin, maintenance, loss and regain of SI.