Protein N-terminal acetylation (Nt-acetylation) is an important mediator of protein function, stability, sorting, and localization. Although the responsible enzymes are thought to be fairly well characterized, the lack of identified in vivo substrates, the occurrence of Nt-acetylation substrates displaying yet uncharacterized N-terminal acetyltransferase (NAT) specificities, and emerging evidence of posttranslational Nt-acetylation, necessitate the use of genetic models and quantitative proteomics. NatB, which targets Met-Glu-, Met-Asp-, and Met-Asn-starting protein N termini, is presumed to Nt-acetylate 15% of all yeast and 18% of all human proteins. We here report on the evolutionary traits of NatB from yeast to human and demonstrate that ectopically expressed hNatB in a yNatB-Delta yeast strain partially complements the natB-Delta phenotypes and partially restores the yNatB Nt-acetylome. Overall, combining quantitative N-terminomics with yeast studies and knockdown of hNatB in human cell lines, led to the unambiguous identification of 180 human and 110 yeast NatB substrates. Interestingly, these substrates included Met-Gln- N-termini, which are thus now classified as in vivo NatB substrates. We also demonstrate the requirement of hNatB activity for maintaining the structure and function of actomyosin fibers and for proper cellular migration. In addition, expression of tropomyosin-1 restored the altered focal adhesions and cellular migration defects observed in hNatB-depleted HeLa cells, indicative for the conserved link between NatB, tropomyosin, and actin cable function from yeast to human.