Efficient, site-specific, and bio-orthogonal conjugation of chemical functionalities to proteins is of great utility in fundamental research as well as industrial processes (e.g., the production of antibody-drug conjugates and immobilization of enzymes for biocatalysis). A popular approach involves reacting a free N-terminal cysteine with a variety of electrophilic reagents. However, current methods for generating proteins with N-terminal cysteines have significant limitations. Herein we report a novel, efficient, and convenient method for producing recombinant proteins with free N-terminal cysteines by genetically fusing a Met-Pro-Cys sequence to the N-terminus of a protein of interest and subjecting the recombinant protein to the sequential action of methionine and proline aminopeptidases. The resulting protein was site-specifically labeled at the N-terminus with fluorescein and a cyclic cell-penetrating peptide through native chemical ligation and a 2-cyanobenzothiazole moiety, respectively. In addition, the optimal recognition sequence of Aeromonas sobria proline aminopeptidase was determined by screening a combinatorial peptide library and incorporated into the N-terminus of a protein of interest for most efficient N-terminal processing.