We present the first large-scale survey of N-terminal protein maturation in archaea based on 873 proteomically identified N-terminal peptides from the two haloarchaea Halobacterium salinarum and Natronomonas pharaonis. The observed protein maturation pattern can be attributed to the combined action of methionine aminopeptidase and N-terminal acetyltransferase and applies to cytosolic proteins as well as to a large fraction of integral membrane proteins. Both N-terminal maturation processes primarily depend on the amino acid in penultimate position, in which serine and threonine residues are over represented. Removal of the initiator methionine occurs in two-thirds of the haloarchaeal proteins and requires a small penultimate residue, indicating that methionine aminopeptidase specificity is conserved across all domains of life. While N-terminal acetylation is rare in bacteria, our proteomic data show that acetylated N termini are common in archaea affecting about 15% of the proteins and revealing a distinct archaeal N-terminal acetylation pattern. Haloarchaeal N-terminal acetyltransferase reveals narrow substrate specificity, which is limited to cleaved N termini starting with serine or alanine residues. A comparative analysis of 140 ortholog pairs with identified N-terminal peptide showed that acetylatable N-terminal residues are predominantly conserved amongst the two haloarchaea. Only few exceptions from the general N-terminal acetylation pattern were observed, which probably represent protein-specific modifications as they were confirmed by ortholog comparison.