Small RNAs (sRNAs) play a pivotal role in bacterial gene regulation. However, the sRNAs of the vast majority of bacteria with sequenced genomes still remain unknown since sRNA genes are usually difficult to recognize and thus not annotated. Here, expression of seven sRNAs (BjrC2a, BjrC2b, BjrC2c, BjrC68, BjrC80, BjrC174 and BjrC1505) predicted by genome comparison of Bradyrhizobium and Rhodopseudomonas members, was verified by RNA gel blot hybridization, microarray and deep sequencing analyses of RNA from the soybean symbiont Bradyrhizobium japonicum USDA 110. BjrC2a, BjrC2b and BjrC2c belong to the RNA family RF00519, while the other sRNAs are novel. For some of the sRNAs we observed expression differences between free-living bacteria and bacteroids in root nodules. The amount of BjrC1505 was decreased in nodules. By contrast, the amount of BjrC2a, BjrC68, BjrC80, BjrC174 and the previously described 6S RNA was increased in nodules, and accumulation of truncated forms of these sRNAs was observed. Comparative genomics and deep sequencing suggest that BjrC2a is an antisense RNA regulating the expression of inositol-monophosphatase. The analyzed sRNAs show a different degree of conservation in Rhizobiales, and expression of homologs of BjrC2, BjrC68, BjrC1505, and 6S RNA was confirmed in the free-living purple bacterium Rhodopseudomonas palustris 5D.