Post-transcriptional control of gene expression allows plants to rapidly adapt to changes in their environment. Under low nitrogen conditions, legume plants engage into a symbiosis with soil bacteria that results in the formation of root nodules, where bacteria are allocated and fix atmospheric nitrogen for the plant's benefit. Recent studies highlighted the importance of small RNA-mediated mechanisms in the control of bacterial infection, nodule organogenesis, and the long-distance signaling that balances plant growth and nodulation. Examples of such mechanisms are shoot-to-root mobile microRNAs and small RNA fragments derived from degradation of bacterial transfer RNAs that repress complementary mRNAs in the host plant. Mechanisms of selective mRNA translation also contribute to rapidly modulate the expression of nodulation genes in a cell-specific manner during symbiosis. Here, the most recent advances made on the regulation of mRNA stability and translatability, and the emerging roles of long non-coding RNAs in symbiosis are summarized.