Legionella pneumophila causes a severe pneumonia known as Legionnaires’ disease. During the infection, Legionella injects more than 300 effector proteins into host cells. Among them are enzymes involved in altering the host-ubiquitination system. Here, we identified two LegionellaOTU (ovarian tumor)-like deubiquitinases (LOT-DUBs; LotB [Lpg1621/Ceg23] and LotC [Lpg2529]). The crystal structure of the LotC catalytic core (LotC_14-310) was determined at 2.4 Å. Unlike the classical OTU-family, the LOT-family shows an extended helical lobe between the Cys-loop and the variable loop, which defines them as a unique class of OTU-DUBs. LotB has an additional ubiquitin-binding site (S1’), which enables the specific cleavage of Lys63-linked polyubiquitin chains. By contrast, LotC only contains the S1 site and cleaves different species of ubiquitin chains. MS analysis of LotB and LotC identified different categories of host-interacting proteins and substrates. Together, our results provide new structural insights into bacterial OTU-DUBs and indicate distinct roles in host–pathogen interactions.