An unusual deubiquitinating (DUB) activity exists in HeLa cell extracts that is highly specific for cleaving K63-linked but not K48-linked polyubiquitin chains. The activity is insensitive to both N-ethyl-maleimide and ubiquitin aldehyde, indicating that it lacks an active site cysteine residue, and gel filtration experiments show that it resides in a high molecular weight (approximately 600 kDa) complex. Using a biochemical approach, we found that the K63-specific DUB activity co-fractionated through seven chromatographic steps with three multisubunit complexes: the 19S (PA700) portion of the 26S proteasome, the COP9 signalosome (CSN) and a novel complex that includes the JAMM/MPN+ domain-containing protein Brcc36. When we analysed the individual complexes, we found that the activity was intrinsic to PA700 and the Brcc36 isopeptidase complex (BRISC), but that the CSN-associated activity was due entirely to an interaction with Brcc36. None of the complexes cleave K6, K11, K29, K48 or alpha-linked polyubiquitin, but they do cleave K63 linkages within mixed-linkage chains. Our results suggest that specificity for K63-linked polyubiquitin is a common property of the JAMM/MPN+ family of DUBs.