The BUZ/Znf-UBP domain is a distinct ubiquitin-binding module found in the cytoplasmic deacetylase HDAC6, the E3 ubiquitin ligase BRAP2/IMP, and a subfamily of deubiquitinating enzymes. Here, we report the solution structure of the BUZ domain of Ubp-M, a ubiquitin-specific protease, and its interaction with ubiquitin. Unlike the BUZ domain from isopeptidase T (isoT) that contains a single zinc finger, the Ubp-M BUZ domain features three zinc-binding sites consisting of 12 residues. These zinc ligands form a pair of cross-braced ring fingers encapsulated within a third zinc finger in the primary structure. In contrast to isoT, which can form an N-terminal loop swapped dimer in the crystal state, the formation of additional zinc fingers in the Ubp-M BUZ domain restricts its N-terminal loop to intra-domain interactions. The ubiquitin-binding site of the Ubp-M BUZ domain is mapped to the highly conserved, concave surface formed by the alpha 3 helix and the central beta-sheet. We further show that this site binds to the C-terminal tail of free ubiquitin, and corresponding peptides display essentially the same binding affinities as full-length ubiquitin does for the Ubp-M BUZ domain. However, modification of the G76(Ub) carboxylate group either by a peptide or isopeptide bond abolishes BUZ-domain interaction. The unique ubiquitin-recognition mode of the BUZ domain family suggests that they may function as "sensors" of free ubiquitin in cells to achieve regulatory roles in many aspects of ubiquitin-dependent processes.