Nα-acetyltransferases (Nats) possess a wide range of important biological functions. Their structures can vary according to the first two residues of their substrate. However, the mechanisms of substrate recognition and catalysis of Nats are elusive. Here, we present two structure of Sulfolobus solfataricus Ard1 (SsArd1), a member of the NatA family, at 2.13 and 1.84 Å. Both structures contain coenzyme A, while the latter also contains a substrate-derived peptide. Sequential structure-based mutagenesis revealed that mutations of critical residues for CoA binding decreased the binding affinity of SsArd1 by 3 ~ 7-fold. Superimposition of SsArd1 (NatA) with human Naa50p (NatE) showed significant differences in key residues of enzymes near the first amino-acid position of the substrate peptide (Glu35 for SsArd1 and Val29 for Naa50p). Further enzyme activity assays revealed that the substrate specificity of SsArd1 could be altered from SSGTPT to MEEKVG by a range of Glu35 mutants. These studies provide not only a molecular elucidation of substrate recognition and specificity for the NatA family, but also insight into how members of the NAT family distinguish between amino acids at the substrate N-terminus from the ancient monomeric archaeal Ard1.