Among the environmental stresses experienced by bacteria, temperature shifts are one of the most important. In this study, we discovered a novel cold adaptation mechanism in Shewanella oneidensis that occurs at the DNA level and is regulated by cryptic prophage excision. Previous studies on bacterial cold tolerance mainly focus on the structural change of cell membrane and changes at the RNA and protein levels. Whether or not genomic change can also contribute to this process has not been explored. Here we employed a whole-genome deep-sequencing method to probe the changes at DNA level in a model psychrotrophic bacteria strain. We found that temperature downshift induced a 10 000-fold increase of the excision of a novel P4-like cryptic prophage. Importantly, although prophage excision only occurred in a relatively small population of bacteria, it was able to facilitate biofilm formation and promote the survival of the entire population. This prophage excision affected cell physiology by disrupting a critical gene encoding transfer-messenger RNA (tmRNA). In addition, we found that the histone-like nucleoid-structuring protein (H-NS) could silence prophage excision via binding to the promoter of the putative excisionase gene at warm temperatures. H-NS level was reduced at cold temperatures, leading to de-repression of prophage excision. Collectively, our results reveal that cryptic prophage excision acts as a regulatory switch to enable the survival of the host at low temperature by controlling the activity of tmRNA and biofilm formation.