Since the discovery of ubiquitin conjugation as a cellular mechanism that triggers proteasomal degradation, the mode of substrate recognition by the ubiquitin-ligation system has been the holy grail of research in the field. This entails the discovery of recognition determinants within protein substrates, which are part of a degron, and explicit E3 ubiquitin (Ub)-protein ligases that trigger their degradation. Indeed, many protein substrates and their cognate E3's have been discovered in the past 40 years. In the course of these studies, various degrons have been randomly identified, most of which are acquired through post-translational modification, typically, but not exclusively, protein phosphorylation. Nevertheless, acquired degrons cannot account for the vast diversity in cellular protein half-life times. Obviously, regulation of the proteome is largely determined by inherent degrons, that is, determinants integral to the protein structure. Inherent degrons are difficult to predict since they consist of diverse sequence and secondary structure features. Therefore, unbiased methods have been employed for their discovery. This review describes the history of degron discovery methods, including the development of high throughput screening methods, state of the art data acquisition and data analysis. Additionally, it summarizes major discoveries that led to the identification of cognate E3 ligases and hitherto unrecognized complexities of degron function. Finally, we discuss future perspectives and what still needs to be accomplished towards achieving the goal of understanding how the eukaryotic proteome is regulated via coordinated action of components of the ubiquitin-proteasome system.