The evolution from outcrossing based on self-incompatibility (SI) to a selfing system is one of the most prevalent transitions in flowering plants. It has been suggested that the loss of SI in Arabidopsis thaliana is associated with pseudogene formation at the SCR male component of the S locus. Recent work, however, suggests that alternative alleles with large deletions at the S locus are also present and may be responsible for the evolution of self-compatibility in this species. We demonstrate that most of these deletion alleles are evolutionarily derived from an S haplotype (haplogroups A) that already possessed the SCR pseudogene. This haplotype and its deletion variants are nearly fixed in Europe. Together with previous transgenic data, these results suggest that the pseudogenization of PsiSCR1 gene changed the SI phenotype in the majority of A. thaliana accessions, and was a critical step in the evolution of selfing in this species. Two other haplogroups (B and C) were also identified, the former of which contains a novel and possibly functional SCR allele. In contrast to haplogroups A, these two haplogroups are found primarily in Africa and Asia. These results suggest that self-compatibility, which appears to be fixed in this species, arose multiple times with different genetic bases, and indicates that a species-specific trait is associated with parallel evolution at the molecular level.