RNA structure plays roles in myriad cellular events including transcription, translation, and RNA processing. Genome-wide analyses of RNA secondary structure in vivo by chemical probing have revealed critical structural features of mRNAs and long ncRNAs. Here, we examine the in vivo secondary structure of a small RNA class, tRNAs. Study of tRNA structure is challenging because tRNAs are heavily modified and strongly structured. We introduce “tRNA structure-seq,” a new workflow that accurately determines in vivo secondary structures of tRNA. The workflow combines dimethyl sulfate (DMS) probing, ultra-processive RT, and mutational profiling (MaP), which provides mutations opposite DMS and natural modifications thereby allowing multiple modifications to be identified in a single read. We applied tRNA structure-seq to E. coli under control and stress conditions. A leading folding algorithm predicts E. coli tRNA structures with only ∼80% average accuracy from sequence alone. Strikingly, tRNA structure-seq, by providing experimental restraints, improves structure prediction under in vivo conditions to ∼95% accuracy, with more than 14 tRNAs predicted completely correctly. tRNA structure-seq also quantifies the relative levels of tRNAs and their natural modifications at single nucleotide resolution, as validated by LC-MS/MS. Our application of tRNA structure-seq yields insights into tRNA structure in living cells, revealing that it is not immutable but has dynamics, with partial unfolding of secondary and tertiary tRNA structure under heat stress that is correlated with a loss of tRNA abundance. This method is applicable to other small RNAs, including those with natural modifications and highly structured regions.