The prevalence and characteristics of small regulatory RNAs (sRNAs) have not been well characterized for Bacillus subtilis, an important model system for Gram-positive bacteria. However, B. subtilis was recently found to synthesize many candidate sRNAs during stationary phase. In the current study, we performed deep sequencing on Hfq-associated RNAs and found that a small subset of sRNAs associates with Hfq, an enigmatic RNA-binding protein that stabilizes sRNAs in Gram-negatives, but whose role is largely unknown in Gram-positive bacteria. We also found that Hfq associated with antisense RNAs, antitoxin transcripts, and many mRNA leaders. Several new candidate sRNAs and mRNA leader regions were also discovered by this analysis. Additionally, mRNA fragments overlapping with start or stop codons associated with Hfq, while, in contrast, relatively few full-length mRNAs were recovered. Deletion of hfq reduced the intracellular abundance of several representative sRNAs, suggesting that B. subtilis Hfq-sRNA interactions may be functionally significant in vivo. In general, we anticipate this catalog of Hfq-associated RNAs to serve as a resource in the functional characterization of Hfq in B. subtilis.