Self-incompatibility (SI) is a genetically controlled system adopted by many flowering plants to avoid inbreeding and thus to maintain species diversity. Generally, self-pollen rejection occurs through active pollen and pistil recognition and subsequent signaling responses. So far, three different molecular controls of pollen and pistil recognition have been characterized and are exemplified by three families: the Solanaceae, the Papaveraceae, and the Brassicaceae. With more components involved in these SI systems coming to light, recent studies have provided intriguing insights into the downstream reactions that follow the initial SI signal perception. The process of pollen rejection is closely associated with rapid and effective proteolytic events, including the ubiquitin-proteasome pathway and the vacuolar sorting pathway. Here, we review our current understanding of the roles of proteolysis in SI responses of flowering plants.