Ubiquitin (Ub) chains regulate many cellular processes, but several chain types including Lys6 linkages have remained unstudied. Here we analyze the bacterial effector E3 ligase NleL (non-Lee-encoded effector ligase) from enterohemorrhagic Escherichia coli (EHEC) O157:H7, which assembles Lys6- and Lys48-linked Ub polymers. Using linkage-specific human deubiquitinases (DUBs) we show that NleL generates heterotypic Ub chains, and branched chains are efficiently hydrolyzed by DUBs. USP family DUBs cleave Lys6-linked polymers exclusively from the distal end, whereas a DUB with preference for Lys6 can cleave Lys6-linked polymers at any position in the chain. We used NleL to generate large quantities of Lys6-linked polyUb. Crystallographic and NMR spectroscopy analyses revealed that an asymmetric interface between Ile44 and Ile36 hydrophobic patches of neighboring Ub moieties is propagated in longer Lys6-linked Ub chains. Interactions via the Ile36 patch can displace Leu8 from the Ile44 patch, leading to marked structural perturbations of Ub.