Nitrous oxide (N2O) is a stable, ozone depleting greenhouse gas. Emissions of N2O into the atmosphere continue to rise, primarily due to the use of nitrogen-containing fertilizers by soil denitrifying microbes. It is clear more effective mitigation strategies are required to reduce emissions. One way to help develop future mitigation strategies is to address the currently poor understanding of transcriptional regulation of the enzymes used to produce and consume N2O. With this ultimate aim in mind we performed RNA-seq on a model soil denitrifier, Paracoccus denitrificans, cultured anaerobically under high N2O and low N2O emitting conditions, and aerobically under zero N2O emitting conditions to identify small RNAs (sRNAs) with potential regulatory functions transcribed under these conditions. sRNAs are short (∼40–500 nucleotides) non-coding RNAs that regulate a wide range of activities in many bacteria. 167 sRNAs were identified throughout the P. denitrificans genome which are either present in intergenic regions or located antisense to ORFs. Furthermore, many of these sRNAs are differentially expressed under high N2O and low N2O emitting conditions respectively, suggesting they may play a role in production or reduction of N2O. Expression of 16 of these sRNAs have been confirmed by RT-PCR. 90% of the sRNAs are predicted to form secondary structures. Predicted targets include transporters and a number of transcriptional regulators. A number of sRNAs were conserved in other members of the α-proteobacteria. Better understanding of the sRNA factors which contribute to expression of the machinery required to reduce N2O will, in turn, help to inform strategies for mitigation of N2O emissions.