It has previously been established that sequences at the C termini of polypeptide substrates are critical for efficient hydrolysis by the ClpP/ClpX ATP-dependent protease. We report for the bacteriophage lambda O replication protein, however, that N-terminal sequences play the most critical role in facilitating proteolysis by ClpP/ClpX. The N-terminal portion of lambda O is degraded at a rate comparable with that of wild type O protein, whereas the C-terminal domain of O is hydrolyzed at least 10-fold more slowly. Consistent with these results, deletion of the first 18 amino acids of lambda O blocks degradation of the N-terminal domain, whereas proteolysis of the O C-terminal domain is only slightly diminished as a result of deletion of the C-terminal 15 amino acids. We demonstrate that ClpX retains its capacity to bind to the N-terminal domain following removal of the first 18 amino acids of O. However, ClpX cannot efficiently promote the ATP-dependent binding of this truncated O polypeptide to ClpP, the catalytic subunit of the ClpP/ClpX protease. Based on our results with lambda O protein, we suggest that two distinct structural elements may be required in substrate polypeptides to enable efficient hydrolysis by the ClpP/ClpX protease: (i) a ClpX-binding site, which may be located remotely from substrate termini, and (ii) a proper N- or C-terminal sequence, whose exposure on the substrate surface may be induced by the binding of ClpX.