The mechanisms by which gene expression is regulated by oxygen are of considerable interest from basic science and therapeutic perspectives. Using mass spectrometric analyses of Saccharomyces cerevisiae ribosomes, we found that the amino acid residue in closest proximity to the decoding center, Pro-64 of the 40S subunit ribosomal protein Rps23p (RPS23 Pro-62 in humans) undergoes posttranslational hydroxylation. We identify RPS23 hydroxylases as a highly conserved eukaryotic subfamily of Fe(II) and 2-oxoglutarate dependent oxygenases; their catalytic domain is closely related to transcription factor prolyl trans-4-hydroxylases that act as oxygen sensors in the hypoxic response in animals. The RPS23 hydroxylases in S. cerevisiae (Tpa1p), Schizosaccharomyces pombe and green algae catalyze an unprecedented dihydroxylation modification. This observation contrasts with higher eukaryotes, where RPS23 is monohydroxylated; the human Tpa1p homolog OGFOD1 catalyzes prolyl trans-3-hydroxylation. TPA1 deletion modulates termination efficiency up to ∼10-fold, including of pathophysiologically relevant sequences; we reveal Rps23p hydroxylation as its molecular basis. In contrast to most previously characterized accuracy modulators, including antibiotics and the prion state of the S. cerevisiae translation termination factor eRF3, Rps23p hydroxylation can either increase or decrease translational accuracy in a stop codon context-dependent manner. We identify conditions where Rps23p hydroxylation status determines viability as a consequence of nonsense codon suppression. The results reveal a direct link between oxygenase catalysis and the regulation of gene expression at the translational level. They will also aid in the development of small molecules altering translational accuracy for the treatment of genetic diseases linked to nonsense mutations.