Sustainable-forage production is globally increasing, especially in marginal areas where the edaphic conditions for plant growth are not optimal. Soil salinization influences the symbiotic interaction between alfalfa and rhizobia. The efficiency of different symbiotic pairs (Sinorhizobium meliloti—Medicago sativa) was evaluated in relation to NaCl application (100 mM) on two different alfalfa cultivars (Marina and Etrusca) and 21 S. meliloti strains isolated in Algeria. At 100 mM NaCl, it was observed that there was a higher variability of plant dry weight compared to the control. The strains able to improve plant growth at 100 mM NaCl were different and specific for each alfalfa cultivar, highlighting that (symbiont) G × (host) G interaction is magnified under stressed (saline) conditions (E). Three strains were then identified as candidate inoculants for M. sativa cv Marina and used for an in-field experiment with induced stress (no irrigation), together with S. meliloti GR4 (a highly competitive strain). In-field experiments, showed a high variability, and a significant difference of plant biomass was observed only for those inoculated with S. meliloti GR4. Obtained results suggest that multiple traits should be considered for inoculant-strain selection, and for an efficient translation from lab to field, it requires extensive comprehension of the mechanisms driving G × G × E interaction.