Hs1VU in E. coli is a new type of ATP-dependent protease composed of two heat shock proteins, the HslU ATPase and the HslV peptidase related to certain beta-type subunits of the 20S proteasome. Here we show that the ATP-dependent hydrolysis of N-carbobenzoxy-Gly-Gly-Leu-7-amido-4-methylcoumarin by the HslVU protease can be markedly stimulated by poly-L-lysine, that is known to activate the casein-degrading activity of the 20S proteasome. However, poly-L-lysine showed little or no effect on the peptidase activity of HslV itself. Instead, it stimulated the hydrolysis of ATP by HslU several-fold. Histone that could stimulate the ATPase activity of HslU also increased the rate of the ATP-dependent peptide hydrolysis by HslV, although to a much lesser extent than by poly-L-lysine. Thus, the poly-L-lysine-mediated increase in the ATPase activity of HslU appears to be responsible for the dramatic activation of the ATP-dependent peptide hydrolysis by HslV. These results suggest that, in the reconstituted HslVU complex, the peptide hydrolysis by HslV occurs in a tightly coupled process with the cleavage of ATP by HslU.