E3 ubiquitin ligases (E3s) confer specificity of protein degradation through ubiquitination of substrate proteins. Yet, the vast majority of the >600 human E3s have no known substrates. To identify proteolytic E3-substrate pairs at scale, we developed combinatorial mapping of E3 targets (COMET), a framework for testing the role of many E3s in degrading many candidate substrates within a single experiment. We applied COMET to SCF ubiquitin ligase subunits that mediate degradation of target substrates (6,716 F-box-ORF [open reading frame] combinations) and E3s that degrade short-lived transcription factors (TFs) (26,028 E3-TF combinations). Our data suggest that many E3-substrate relationships are complex rather than 1:1 associations. Finally, we leverage deep learning to predict the structural basis of E3-substrate interactions and probe the strengths and limits of such models. Looking forward, we consider the practicality of transposing this framework, i.e., computational structural prediction of all possible E3-substrate interactions, followed by multiplex experimental validation.