DNA double-strand breaks (DSBs) are perhaps the most toxic of all DNA lesions, with defects in the DNA-damage response to DSBs being associated with various human diseases. Although it is known that DSB repair pathways are tightly regulated by ubiquitylation, we do not yet have a comprehensive understanding of how deubiquitylating enzymes (DUBs) function in DSB responses. Here, by carrying out a multidimensional screening strategy for human DUBs, we identify several with hitherto unknown links to DSB repair, the G2/M DNA-damage checkpoint and genome-integrity maintenance. Phylogenetic analyses reveal functional clustering within certain DUB subgroups, suggesting evolutionally conserved functions and/or related modes of action. Furthermore, we establish that the DUB UCHL5 regulates DSB resection and repair by homologous recombination through protecting its interactor, NFRKB, from degradation. Collectively, our findings extend the list of DUBs promoting the maintenance of genome integrity, and highlight their potential as therapeutic targets for cancer.