The ribosomal synthesis of proteins in the eukaryotic cytosol has always been thought to start from the unformylated N-terminal (Nt) methionine (Met). In contrast, in virtually all nascent proteins in bacteria and eukaryotic organelles, such as mitochondria and chloroplasts, Nt-formyl-methionine (fMet) is the first building block of ribosomal synthesis. Through extensive approaches, including mass spectrometric analyses of the N-termini of proteins and molecular genetic techniques with an affinity-purified antibody for Nt-formylation, we investigated whether Nt-formylated proteins could also be produced and have their own metabolic fate in the cytosol of a eukaryote, such as yeast Saccharomyces cerevisiae. We discovered that Nt-formylated proteins could be generated in the cytosol by yeast mitochondrial formyltransferase (Fmt1). These Nt-formylated proteins were massively upregulated in the stationary phase or upon starvation for specific amino acids and were crucial for the adaptation to specific stresses. The stress-activated kinase Gcn2 was strictly required for the upregulation of Nt-formylated proteins by regulating the activity of Fmt1 and its retention in the cytosol. We also found that the Nt-fMet residues of Nt-formylated proteins could be distinct N-terminal degradation signals, termed fMet/N-degrons, and that Psh1 E3 ubiquitin ligase mediated the selective destruction of Nt-formylated proteins as the recognition component of a novel eukaryotic fMet/N-end rule pathway, termed fMet/N-recognin.