Legionella pneumophila manipulates a wide array of host cellular processes during infection; one that appears to be highly altered is the ubiquitination pathway. The SidE family of Legionella effector proteins has been shown to modify target proteins via a novel ubiquitination pathway, in which phosphoribosyl-ubiquitin is generated and subsequently used to ubiquitinate proteins. To elucidate the biochemical mechanism of this novel modification, we have solved the crystal structure of the catalytic core of SidE family member, SdeA. Using biochemical activity assays, we discovered an unpredicted domain that is crucial for the first step of this novel modification. To elucidate the molecular mechanism, we co-crystallized another SidE family member, SdeD, with both unmodified and modified ubiquitin molecules. These structural studies gave insights into the mechanism of ubiquitin modification during the second step of the reaction. We have also shown that two of the small SidE family members, SdeD and SdeF, remove the SdeA ubiquitin modification in an activity dependent manner, thus functioning as a deubiquitinase towards SdeA target proteins. These deubiquitinase proteins have also been shown to revert the phenotype exerted by SdeA in host cells. Altogether, this work provides a mechanistic insight into a novel ubiquitination reaction catalyzed by SdeA, in addition to providing a preliminary model for regulation of this enzymatic activity.