The cycle inhibiting factors (Cifs) are a family of translocated effector proteins, found in diverse pathogenic bacteria, that interfere with the host cell cycle by catalyzing the deamidation of a specific glutamine residue (Gln40) in NEDD8 and the related protein ubiquitin. This modification prevents recycling of neddylated cullin-RING ligases, leading to stabilization of various cullin-RING ligase targets, and also prevents polyubiquitin chain formation. Here, we report the crystal structures of two Cif/NEDD8 complexes, revealing a conserved molecular interface that defines enzyme/substrate recognition. Mutation of residues forming the interface suggests that shape complementarity, rather than specific individual interactions, is a critical feature for complex formation. We show that Cifs from diverse bacteria bind NEDD8 in vitro and conclude that they will all interact with their substrates in the same way. The “occluding loop” in Cif gates access to Gln40 by forcing a conformational change in the C terminus of NEDD8. We used native PAGE to follow the activity of Cif from the human pathogen Yersinia pseudotuberculosis and selected variants, and the position of Gln40 in the active site has allowed us to propose a catalytic mechanism for these enzymes.