Deubiquitylating enzymes (DUBs) enhance the dynamics of the versatile ubiquitin (Ub) code by reversing and regulating cellular ubiquitylation processes at multiple levels. Here we discovered that the uncharacterized human protein ZUFSP (zinc finger with UFM1-specific peptidase domain protein/C6orf113/ZUP1), which has been annotated as a potentially inactive UFM1 protease, and its fission yeast homolog Mug105 define a previously unrecognized class of evolutionarily conserved cysteine protease DUBs. Human ZUFSP selectively interacts with and cleaves long K63-linked poly-Ub chains by means of tandem Ub-binding domains, whereas it displays poor activity toward mono- or di-Ub substrates. In cells, ZUFSP is recruited to and regulates K63-Ub conjugates at genotoxic stress sites, promoting chromosome stability upon replication stress in a manner dependent on its catalytic activity. Our findings establish ZUFSP as a new type of linkage-selective cysteine peptidase DUB with a role in genome maintenance pathways.