Histone ubiquitylation is implicated in many cellular processes that include transcriptional regulation and DNA damage repair. In yeast, monoubiquitylation on lysine 123 residue of histone H2B is mediated by Rad6 E2 ubiquitin conjugating enzyme and Bre1 E3 ubiquitin ligase. Interestingly, our biochemical analyses previously showed that Rad6 binds to the N-terminal coiled-coil motif (CCM) of Bre1 while most E2 enzymes interact with RING-finger domains within their cognate E3 enzymes. To understand detailed structural basis for Rad6-Bre1 interaction, we solved the crystal structure of Rad6-Bre1 CCM complex at 2.1Å resolution and deployed in vitro protein interaction and H2B ubiquitylation analyses with purified factors to validate obtained structural model. We found that Bre1 CCM anchors to the backside of Rad6 and this unique Rad6-Bre1 recognition mode directs histone H2B monoubiquitylation rather than polyubiquitylation. In addition, two Bre1 CCM monomers form a homodimer in an asymmetric manner with each adopting a distinct conformation. This explains why two Bre1 homologs, Bre1A and Bre1B, are evolved to form a heterodimeric E3 enzyme in higher eukaryotes. Our structural study reveals a novel RING-finger independent interaction of Rad6 and Bre1 and establishes the molecular mechanism of H2B monoubiquitylation.