The nolR gene encodes a negatively acting, transcriptional regulatory protein of core Nod-factor biosynthetic genes in the sinorhizobia. Although previous reports showed that nolR modulates Nod-factor production and enhances nodulation speed of Sinorhizobium meliloti on alfalfa, there have been no reports for the symbiotic function of this gene in the S. medicae–Medicago truncatula symbiosis. Here, we constructed an nolR mutant of S. medicae WSM419 and evaluated mutant and wild-type strains for their nodulation ability, competitiveness, host specificity, and density-dependent nodulation phenotypes. When the mutant was inoculated at low and medium population densities, it showed enhanced nodule formation during the initial stages of nodulation. Results of quantitative competitive nodulation assays indicated that an nolR mutant had 2.3-fold greater competitiveness for nodulation on M. truncatula ‘A17’ than did the wild-type strain. Moreover, the nodulation phenotype of the nolR mutant differed among Medicago genotypes and showed significantly enhanced nodule development on M. tricycla. Taken together, these results indicated that mutation of nolR in S. medicae positively influenced nodule initiation, competitive nodulation, and nodule development at later nodulation stages. This may allow nolR mutants of S. medicae to have a selective advantage under field conditions.