In bacteria, nascent proteins bear the pretranslationally generated N-terminal (Nt) formyl-methionine (fMet) residue. Nt-fMet of bacterial proteins is a degradation signal, termed fMet/N-degron. By contrast, proteins synthesized by cytosolic ribosomes of eukaryotes were presumed to bear unformylated Nt-Met. Here we found that the yeast formyltransferase Fmt1, although imported into mitochondria, could also produce Nt-formylated proteins in the cytosol. Nt-formylated proteins were strongly up-regulated in stationary phase or upon starvation for specific amino acids. This up-regulation strictly required the Gcn2 kinase, which phosphorylates Fmt1 and mediates its retention in the cytosol. We also found that the Nt-fMet residues of Nt-formylated proteins act as fMet/N-degrons and identified the Psh1 ubiquitin ligase as the recognition component of the eukaryotic fMet/N-end rule pathway, which destroys Nt-formylated proteins.