The oral commensal Fusobacterium nucleatum can spread to extra-oral sites where it is associated with diverse pathologies including pre-term birth and cancer. Due to the evolutionary distance of F. nucleatum to other model bacteria, we lack a deeper understanding of RNA regulatory networks that allow this bacterium to adapt to its various niches. As a first step in that direction, we recently showed that F. nucleatum harbors a global stress response governed by the extracytoplasmic function sigma factor σE, which displays a striking functional conservation with Proteobacteria and includes a noncoding arm in the form of a regulatory small RNA (sRNA), FoxI. To search for putative additional σE-dependent sRNAs, we comprehensively mapped 5’- and 3’-ends of transcripts in the model strain ATCC 23726. This enabled the discovery of FoxJ, a ~156 nucleotide sRNA previously misannotated as the 5’ UTR of ylmH. FoxJ is tightly controlled by σE and activated by the same stress conditions as FoxI. Both sRNAs act as mRNA repressors of the abundant porin FomA, but FoxJ also regulates genes that are distinct from the target suite of FoxI. Moreover, FoxJ differs from most other σE-dependent sRNAs in that it also positively regulates genes at the post-transcriptional level. We provide preliminary evidence for a new mode of sRNA-mediated mRNA activation, which involves the targeting of intra-operonic terminators. Overall, our study provides an important resource through the comprehensive annotation of 5’- and 3’ UTRs in F. nucleatum and expands our understanding of the σE-response in this evolutionarily distant bacterium.