Protein lifespan is regulated by co-translational modification by several enzymes, including methionine aminopeptidases and N-alpha-aminoterminal acetyltransferases. The NatB enzymatic complex is an N-terminal acetyltransferase constituted by two subunits, NAA20 and NAA25, whose interaction is necessary to avoid NAA20 catalytic subunit degradation. We found that deletion of the first five amino acids of hNAA20 or fusion of a peptide to its amino terminal end abolishes its interaction with hNAA25. Substitution of the second residue of hNAA20 with amino acids with small, uncharged side-chains allows NatB enzymatic complex formation. However, replacement by residues with large or charged side-chains interferes with its hNAA25 interaction, limiting functional NatB complex formation. Comparison of NAA20 eukaryotic sequences showed that the residue following the initial methionine, an amino acid with a small uncharged side-chain, has been evolutionarily conserved. We have confirmed the relevance of second amino acid characteristics of NAA20 in NatB enzymatic complex formation in Drosophila melanogaster. Moreover, we have evidenced the significance of NAA20 second residue in Saccharomyces cerevisiae using different NAA20 versions to reconstitute NatB formation in a yNAA20-KO yeast strain. The requirement in humans and in fruit flies of an amino acid with a small uncharged side-chain following the initial methionine of NAA20 suggests that methionine aminopeptidase action may be necessary for the NAA20 and NAA25 interaction. We showed that inhibition of MetAP2 expression blocked hNatB enzymatic complex formation by retaining the initial methionine of NAA20. Therefore, NatB-mediated protein N-terminal acetylation is dependent on methionine aminopeptidase, providing a regulatory mechanism for protein N-terminal maturation. (C) 2020 Elsevier Ltd. All rights reserved.