Eukaryotic cells use autophagy and the ubiquitin–proteasome system as their major protein degradation pathways. Whereas the ubiquitin–proteasome system is involved in the rapid degradation of proteins, autophagy pathways can selectively remove protein aggregates and damaged or excess organelles. Proteasome-mediated degradation requires previous ubiquitylation of the cargo, which is then recognized by ubiquitin receptors directing it to 26S proteasomes. Although autophagy has long been viewed as a random cytoplasmic degradation system, the involvement of ubiquitin as a specificity factor for selective autophagy is rapidly emerging. Recent evidence also suggests active crosstalk between proteasome-mediated degradation and selective autophagy. Here, we discuss the molecular mechanisms that link autophagy and the proteasome system, as well as the emerging roles of ubiquitin and ubiquitin-binding proteins in selective autophagy. On the basis of the evolutionary history of autophagic ubiquitin receptors, we propose a common origin for metazoan ubiquitin-dependent autophagy and the cytoplasm-to-vacuole targeting pathway of yeast.