Atg5 is covalently modified with a ubiquitin-like modifier, Atg12, and the Atg12-Atg5 conjugate further forms a complex with the multimeric protein Atg16. The Atg12-Atg5·Atg16 multimeric complex plays an essential role in autophagy, the bulk degradation system conserved in all eukaryotes. We have reported here the crystal structure of Atg5 complexed with the N-terminal region of Atg16 at 1.97Å resolution. Atg5 comprises two ubiquitin-like domains that flank a helix-rich domain. The N-terminal region of Atg16 has a helical structure and is bound to the groove formed by these three domains. In vitro analysis showed that Arg-35 and Phe-46 of Atg16 are crucial for the interaction. Atg16, with a mutation at these residues, failed to localize to the pre-autophagosomal structure and could not restore autophagy in Atg16-deficient yeast strains. Furthermore, these Atg16 mutants could not restore a severe reduction in the formation of the Atg8-phosphatidylethanolamine conjugate, another essential factor for autophagy, in Atg16-deficient strains under starvation conditions. These results taken together suggest that the direct interaction between Atg5 and Atg16 is crucial to the performance of their roles in autophagy.