WD40-repeat β-propellers are found in a wide range of proteins involved in distinct biological activities. We define a large subset of WD40 β-propellers as a class of ubiquitin-binding domains. Using the β-propeller from Doa1/Ufd3 as a paradigm, we find the conserved top surface of the Doa1 β-propeller binds the hydrophobic patch of ubiquitin centered on residues I44, L8, and V70. Mutations that disrupt ubiquitin binding abrogate Doa1 function, demonstrating the importance of this interaction. We further demonstrate that WD40 β-propellers from a functionally diverse set of proteins bind ubiquitin in a similar fashion. This set includes members of the F box family of SCF ubiquitin E3 ligase adaptors. Using mutants defective in binding, we find that ubiquitin interaction by the F box protein Cdc4 promotes its autoubiquitination and turnover. Collectively, our results reveal a molecular mechanism that may account for how ubiquitin controls a broad spectrum of cellular activities.