In oligotrophic ocean waters where bacteria are often subjected to chronic nutrient limitation, community transcriptome sequencing has pointed to the presence of highly abundant small RNAs (sRNAs). The role of sRNAs in regulating response to nutrient stress was investigated in a model heterotrophic marine bacterium Ruegeria pomeroyi grown in continuous culture under carbon (C) and nitrogen (N) limitation. RNAseq analysis identified 99 putative sRNAs. Sixty-nine were cis-encoded and located antisense to a presumed target gene. Thirty were trans-encoded and initial target prediction was performed computationally. The most prevalent functional roles of genes anti-sense to the cis-sRNAs were transport, cell-cell interactions, signal transduction, and transcriptional regulation. Most sRNAs were transcribed equally under both C and N limitation, and may be involved in a general stress response. However, 14 were regulated differentially between the C and N treatments and may respond to specific nutrient limitations. A network analysis of the predicted target genes of the R. pomeroyi cis-sRNAs indicated that they average fewer connections than typical protein-encoding genes, and appear to be more important in peripheral or niche-defining functions encoded in the pan genome.