The Rtf1 subunit of the Paf1 complex is required for specific histone modifications, including histone H2B lysine 123 monoubiquitylation. In Saccharomyces cerevisiae, deletion of RTF1 is lethal in the absence of Rkr1, a ubiquitin-protein ligase involved in the destruction of nonstop proteins, which arise from mRNAs lacking stop codons or translational readthrough into the poly(A) tail. We performed a transposon-based mutagenesis screen to identify suppressors of rtf1Δ rkr1Δ lethality and found that a mutation in the gene encoding the protein chaperone Hsp104 rescued viability. Hsp104 plays a role in prion propagation, including the maintenance of [PSI+], which contributes to the synthesis of nonstop proteins. We demonstrate that rtf1Δ and rkr1Δ are synthetically lethal only in the presence of [PSI+]. The deletion, inactivation, and overexpression of HSP104 or the overexpression of prion-encoding genes URE2 and LSM4 clear [PSI+] and rescue rtf1Δ rkr1Δ lethality. In addition, the presence of [PSI+] decreases the fitness of rkr1Δ strains. We investigated whether the loss of RTF1 exacerbates an overload in nonstop proteins in rkr1Δ [PSI+] strains but, using reporter plasmids, found that rtf1Δ decreases nonstop protein levels, indicating that excess nonstop proteins may not be the cause of synthetic lethality. Instead, our data suggest that the loss of Rtf1-dependent histone modifications increases the burden on quality control pathways in cells lacking Rkr1 and containing [PSI+].