Small non-coding regulatory RNAs (sRNAs) post-transcriptionally affect multiple phenotypes in prokaryotes and eukaryotes, yet most of the underlying regulatory mechanisms and the nature of the target mRNAs remain unclear. Here we report the identification and functional analysis of the novel cis-encoded sRNA h2cR, from the human opportunistic pathogen Burkholderia cenocepacia J2315. The sRNA was found to negatively regulate the hfq2 mRNA, through binding to part of the 5′-UTR region of the hfq2 mRNA, resulting in accelerated hfq2 mRNA decay and reduced protein levels in exponentially growing cells. Both the h2cR transcript and the hfq2 mRNA are stabilized by the other B. cenocepacia RNA chaperone, Hfq. Infection experiments using the nematode Caenorhabditis elegans revealed that down-regulation of Hfq2 by h2cR decreases the B. cenocepacia ability to colonize and persist within the nematode, suggesting a role for h2cR on bacterial persistence in the host.