Bacteriophages are large and diverse components of the biosphere, and many phages are temperate. Upon infection, temperate phages can establish lysogeny in which a prophage is typically integrated into the bacterial chromosome. Here, we describe the phenomenon of tRNA-dependent lysogeny, a previously unrecognized behavior of some temperate phages. tRNA-dependent lysogeny is characterized by two unusual features. First, a phage-encoded tyrosine family integrase mediates site-specific recombination between a phage site and a bacterial site overlapping a host tRNA gene. However, and share only a short (~10 bp) common core such that a functional tRNA is not reconstructed upon integration. Second, the phage encodes a tRNA of the same isotype as the disrupted but essential host tRNA, complementing its loss, and consequently is required for the survival of lysogenic progeny. As expected, an integrase-defective phage mutant forms turbid plaques, and bacterial progeny are immune to superinfection, but they lack stability, and the prophage is rapidly lost. In contrast, a tRNA-defective phage mutant forms clear plaques and more closely resembles a repressor mutant, and lysogens are recovered only at very low frequency through the use of secondary attachment sites elsewhere in the host genome. Integration-proficient plasmids derived from these phages must also carry a cognate phage tRNA gene for efficient integration, and these may be useful tools for mycobacterial genetics. We show that tRNA-dependent lysogeny is used by phages within multiple different groups of related viruses and may be prevalent elsewhere in the broader phage community.IMPORTANCEBacteriophages are the most numerous biological entities in the biosphere, and a substantial proportion of phages are temperate, forming stable lysogens in which a prophage copy of the genome integrates into the bacterial chromosome. Many phages encode a variety of tRNA genes whose roles are poorly understood, although it has been proposed that they enhance translational efficiencies in lytic growth or that they counteract host defenses that degrade host tRNAs. Here, we show that phage-encoded tRNAs play key roles in the establishment of lysogeny of some temperate phages. They do so by compensating for the loss of tRNA function when phages integrate at an site overlapping a tRNA gene but fail to reconstruct the tRNA at the attachment junction. In this system of tRNA-dependent lysogeny, the phage-encoded tRNA is required for lysogeny, and deletion of the phage tRNA gives rise to a clear plaque phenotype and obligate lytic growth.