We have performed a computational comparative analysis of six small non-coding RNA (sRNA) families in α-proteobacteria. Members of these families were first identified in the intergenic regions of the nitrogen-fixing endosymbiont S. meliloti by a combined bioinformatics screen followed by experimental verification. Consensus secondary structures inferred from covariance models for each sRNA family evidenced in some cases conserved motifs putatively relevant to the function of trans-encoded base-pairing sRNAs i.e., Hfq-binding signatures and exposed anti Shine-Dalgarno sequences. Two particular family models, namely αr15 and αr35, shared own sub-structural modules with the Rfam model suhB (RF00519) and the uncharacterized sRNA family αr35b, respectively. A third sRNA family, termed αr45, has homology to the cis-acting regulatory element speF (RF00518). However, new experimental data further confirmed that the S. meliloti αr45 representative is an Hfq-binding sRNA processed from or expressed independently of speF, thus refining the Rfam speF model annotation. All the six families have members in phylogenetically related plant-interacting bacteria and animal pathogens of the order of the Rhizobiales, some occurring with high levels of paralogy in individual genomes. In silico and experimental evidences predict differential regulation of paralogous sRNAs in S. meliloti 1021. The distribution patterns of these sRNA families suggest major contributions of vertical inheritance and extensive ancestral duplication events to the evolution of sRNAs in plant-interacting bacteria.