Fusobacterium nucleatum, long known as a constituent of the oral microflora, has recently garnered renewed attention for its association with several different human cancers. The growing interest in this emerging cancer-associated bacterium contrasts with a paucity of knowledge about its basic gene expression features and physiological responses. As fusobacteria lack all established small RNA-associated proteins, post-transcriptional networks in these bacteria are also unknown. In the present study, using differential RNA-sequencing, we generate high-resolution global RNA maps for five clinically relevant fusobacterial strains—F. nucleatum subspecies nucleatum, animalis, polymorphum and vincentii, as well as F. periodonticum—for early, mid-exponential growth and early stationary phase. These data are made available in an online browser, and we use these to uncover fundamental aspects of fusobacterial gene expression architecture and a suite of non-coding RNAs. Developing a vector for functional analysis of fusobacterial genes, we discover a conserved fusobacterial oxygen-induced small RNA, FoxI, which serves as a post-transcriptional repressor of the major outer membrane porin FomA. Our findings provide a crucial step towards delineating the regulatory networks enabling F. nucleatum adaptation to different environments, which may elucidate how these bacteria colonize different compartments of the human body.