Legume plants interact with rhizobia to form nitrogen-fixing root nodules. Legume-rhizobium interactions are specific and only compatible rhizobia and plant species will lead to nodule formation. Even within compatible interactions, the genotype of both the plant and the bacterial symbiont will impact on the efficiency of nodule functioning and nitrogen-fixation activity. The model legume Medicago truncatula forms nodules with several species of the Sinorhizobium genus. However, the efficiency of these bacterial strains is highly variable. In this study, we compared the symbiotic efficiency of Sinorhizobium meliloti strains Sm1021, 102F34, and FSM-MA, and Sinorhizobium medicae strain WSM419 on the two widely used M. truncatula accessions A17 and R108. The efficiency of the interactions was determined by multiple parameters. We found a high effectiveness of the FSM-MA strain with both M. truncatula accessions. In contrast, specific highly efficient interactions were obtained for the A17-WSM419 and R108-102F34 combinations. Remarkably, the widely used Sm1021 strain performed weakly on both hosts. We showed that Sm1021 efficiently induced nodule organogenesis but cannot fully activate the differentiation of the symbiotic nodule cells, explaining its weaker performance. These results will be informative for the selection of appropriate rhizobium strains in functional studies on symbiosis using these M. truncatula accessions, particularly for research focusing on late stages of the nodulation process.