Lon is a conserved AAA+ (ATPases associated with diverse cellular activities) proteolytic machine that plays a key regulatory role in cells under proteotoxic stress. Lon-mediated proteolysis can be stimulated by either the unfolded or specific protein substrates accumulated under stress conditions. However, the molecular basis for this substrate-controlled proteolysis remains unclear. Here, we have found that the heat shock protein LarA, a recently discovered Lon substrate and allosteric activator, binds to the N-terminal domain (NTD) of Lon. The crystal structure of the LarA-NTD complex shows that LarA binds to a highly conserved groove in the NTD through the terminal aromatic residue of its C-terminal degron. Crystallographic and biochemical evidence further reveals that this binding exposes the hydrophobic core of LarA, which can bind a leucine residue and promote local protein unfolding. These results define the mechanistic role of the NTD in regulating Lon-mediated proteolysis in response to varying cellular conditions.