Autophagy is a catabolic cellular process in which unwanted proteins and organelles are degraded by lysosomes. It is characterized by the formation of the double-membrane autophagosome decorated with LC3B, a protein that mediates autophagosomal fusion with lysosomes. The cysteine protease ATG4b acts at two stages in the life cycle of LC3B. We set out to characterize the protein-protein interaction between LC3B and ATG4b. Through biochemical and biophysical studies, we show that the ubiquitin-like core of LC3B (residues 1-115; "LC3B-115"), which lacks the C-terminal cleavage site (between residue 120 and 121), binds to full-length ATG4b with a surprisingly tight dissociation constant (KD) in the low nanomolar range; 10-30-fold tighter than that of the substrate pro-LC3B (residues 1-125) or the product LC3B-I (residues 1-120). Consequently, LC3B-115 is a potent inhibitor of the ATG4b-mediated cleavage of pro-LC3B (IC50 = 15 nM). Binding of the LC3B-115 has no effect on the conformation of the active site of ATG4b, as judged by the turnover of a peptide substrate ("substrate-33"), derived from LC3B-I residues 116-120. Conversely, truncations of ATG4b show that binding and proteolysis of LC3B critically depend on the C-terminal tail of ATG4b, whereas proteolysis of the peptide substrate-33 does not require the C-terminal tail of ATG4b. These results support a bipartite model for LC3B-ATG4b binding in which the core of LC3B binds to ATG4b and the C-terminal tail of pro-LC3B organizes the ATG4b active site; additionally, the C-terminal tail of ATG4b contributes at least 1000-fold higher binding affinity to the LC3B-ATG4b interaction and likely wraps around the LC3B-ubiquitin core. PPIs are often described as containing an energetic "hot spot" for binding; in the case of LC3B-ATG4b, however, the substrate-enzyme complex contains multiple, energetically relevant domains that differentially affect binding affinity and catalytic efficiency.