Three soybean [Glycine max (L) Merr.] small RNA libraries were generated and sequenced using the Illumina platform to examine the role of miRNAs during soybean nodulation. The small RNA libraries were derived from root hairs inoculated with Bradyrhizobium japonicum (In_RH) or mock-inoculated with water (Un_RH), as well as from the comparable inoculated stripped root samples (i.e. inoculated roots with the root hairs removed). Sequencing of these libraries identified a total of 114 miRNAs, including 22 novel miRNAs. A comparison of miRNA abundance among the 114 miRNAs identified 66 miRNAs that were differentially expressed between root hairs and stripped roots, and 48 miRNAs that were differentially regulated in infected root hairs in response to B. japonicum when compared to uninfected root hairs (P ≤ 0.05). A parallel analysis of RNA ends (PARE) library was constructed and sequenced to reveal a total of 405 soybean miRNA targets, with most predicted to encode transcription factors or proteins involved in protein modification, protein degradation and hormone pathways. The roles of gma-miR4416 and gma-miR2606b during nodulation were further analysed. Ectopic expression of these two miRNAs in soybean roots resulted in significant changes in nodule numbers. miRNA target information suggested that gma-miR2606b regulates a Mannosyl-oligosaccharide 1, 2-alpha-mannosidase gene, while gma-miR4416 regulates the expression of a rhizobium-induced peroxidase 1 (RIP1)-like peroxidase gene, GmRIP1, during nodulation.