Protein N(α)-terminal acetylation (Nt-acetylation) is considered one of the most common protein modification in eukaryotes, and 80-90% of all soluble human proteins are modified in this way, with functional implications ranging from altered protein function and stability to translocation potency amongst others. Nt-acetylation is catalyzed by N-terminal acetyltransferases (NATs), and in yeast five NAT types are identified and denoted NatA-NatE. Higher eukaryotes additionally express NatF. Except for NatD, human orthologues for all yeast NATs are identified. yNatD is defined as the catalytic unit Naa40p (Nat4) which co-translationally Nt-acetylates histones H2A and H4. In this study we identified and characterized hNaa40p/hNatD, the human orthologue of the yeast Naa40p. An in vitro proteome-derived peptide library Nt-acetylation assay indicated that recombinant hNaa40p acetylates N-termini starting with the consensus sequence Ser-Gly-Gly-Gly-Lys-, strongly resembling the N-termini of the human histones H2A and H4. This was confirmed as recombinant hNaa40p Nt-acetylated the oligopeptides derived from the N-termini of both histones. In contrast, a synthetically Nt-acetylated H4 N-terminal peptide with all lysines being non-acetylated, was not significantly acetylated by hNaa40p, indicating that hNaa40p catalyzed H4 N(α)-acetylation and not H4 lysine N(ε)-acetylation. Also, immunoprecipitated hNaa40p specifically Nt-acetylated H4 in vitro. Heterologous expression of hNaa40p in a yeast naa40-Δ strain restored Nt-acetylation of yeast histone H4, but not H2A in vivo, probably reflecting the fact that the N-terminal sequences of human H2A and H4 are highly similar to each other and to yeast H4 while the N-terminal sequence of yeast H2A differs. Thus, Naa40p seems to have co-evolved with the human H2A sequence. Finally, a partial co-sedimentation with ribosomes indicates that hNaa40p co-translationally acetylates H2A and H4. Combined, our results strongly suggest that human Naa40p/NatD is conserved from yeast. Thus, the NATs of all classes of N-terminally acetylated proteins in humans now appear to be accounted for.