Both the peptidase activity against small fluorescent peptide substrates and the ATPase activity of Lon (La) proteases are stimulated by unstructured proteins such as α-casein. This stimulation reveals the simultaneous interaction of Lon with two proteolytic substrates—α-casein and the peptide substrate. To understand the cellular function of this stimulation, it is important to determine the physical properties of Lon stimulators. The abilities of compositionally simple random copolymers of amino acids (rcAAs) to stimulate the peptidase and ATPase activities of the Lon protease from Mycobacterium smegmatis (Ms-Lon) and its N-terminal truncation mutant (N-E226) were determined. We report that cationic but not anionic rcAAs stimulated Ms-Lon's peptidase activity but were themselves poor substrates for the enzyme. Peptidase stimulation by rcAAs correlated approximately with the degree of hydrophobicity of these polypeptides and reached levels >10-fold higher than observed previously for Ms-Lon stimulators such as α-casein. In contrast to α-casein, which stimulates Ms-Lon's peptidase activity by 40% and ATPase activity by 150%, rcAAs stimulated peptidase activity without concomitant stimulation of ATPase activity. Active site labeling experiments suggested that both rcAAs and ATP increased peptidase activity by increasing accessibility to the peptidase active site. Peptidase activity assays in the presence of both α-casein and rcAAs revealed that interactions of rcAAs and α-casein with Ms-Lon are extremely complex and not mutually exclusive. Specifically, (1) additions of low concentrations of α-casein (<50 μg/mL) caused a further stimulation of Ms-Lon's rcAA-stimulated peptidase activity; (2) additions of higher concentrations of α-casein inhibited Ms-Lon's rcAA-stimulated peptidase activity; (3) additions of all concentrations of α-casein inhibited N-E226's rcAA-stimulated peptidase activity. We conclude the Ms-Lon can interact with an rcAA, α-casein, and a substrate peptide simultaneously, and that formation of this quaternary complex requires the N-terminal domain of Ms-Lon. These data support models of Ms-Lon that include two allosteric polypeptide binding sites distinct from the catalytic peptidase site.