We developed a novel technique, called pseudouridine site identification sequencing (PSI-seq), for the transcriptome-wide mapping of pseudouridylation sites with single-base resolution from cellular RNAs based on the induced termination of reverse transcription specifically at pseudouridines following CMCT treatment. PSI-seq analysis of RNA samples from S. cerevisiae correctly detected all of the 43 known pseudouridines in yeast 18S and 25S ribosomal RNA with high specificity. Moreover, application of PSI-seq to the yeast transcriptome revealed the presence of site-specific pseudouridylation within dozens of mRNAs, including RPL11a, TEF1, and other genes implicated in translation. To identify the mechanisms responsible for mRNA pseudouridylation, we genetically deleted candidate pseudouridine synthase (Pus) enzymes and reconstituted their activities in vitro. These experiments demonstrated that the Pus1 enzyme was necessary and sufficient for pseudouridylation of RPL11a mRNA, whereas Pus4 modified TEF1 mRNA, and Pus6 pseudouridylated KAR2 mRNA. Finally, we determined that modification of RPL11a at Ψ -68 was observed in RNA from the related yeast S. mikitae, and Ψ -239 in TEF1 mRNA was maintained in S. mikitae as well as S. pombe, indicating that these pseudouridylations are ancient, evolutionarily conserved RNA modifications. This work establishes that site-specific pseudouridylation of eukaryotic mRNAs is a genetically programmed RNA modification that naturally occurs in multiple yeast transcripts via distinct mechanisms, suggesting that mRNA pseudouridylation may provide an important novel regulatory function. The approach and strategies that we report here should be generally applicable to the discovery of pseudouridylation, or other RNA modifications, in diverse biological contexts.