The N-end rule pathway is conserved from bacteria to man and determines the half-life of a protein based on its N-terminal amino acid. In Escherichia coli, model substrates bearing an N-degron are recognised by ClpS and degraded by ClpAP in an ATP-dependent manner. Here, we report the isolation of 23 ClpS-interacting proteins from E. coli. Our data show that at least one of these interacting proteins--putrescine aminotransferase (PATase)--is post-translationally modified to generate a primary N-degron. Remarkably, the N-terminal modification of PATase is generated by a new specificity of leucyl/phenylalanyl-tRNA-protein transferase (LFTR), in which various combinations of primary destabilising residues (Leu and Phe) are attached to the N-terminal Met. This modification (of PATase), by LFTR, is essential not only for its recognition by ClpS, but also determines the stability of the protein in vivo. Thus, the N-end rule pathway, through the ClpAPS-mediated turnover of PATase may have an important function in putrescine homeostasis. In addition, we have identified a new element within the N-degron, which is required for substrate delivery to ClpA.