In the understanding of the molecular interaction between plants and their microbiome, a key point is to identify simplified models of the microbiome including relevant bacterial and fungal partners which could also be effective in plant growth promotion. Here, as proof-of-concept, we aim to identify the possible interactions between symbiotic nitrogen-fixing rhizobia and soil fungi (Trichoderma spp.), hence shed light on synergistic roles rhizospheric fungi could have in the symbiotic nitrogen fixation with host plants. We selected 4 strains of the model rhizobium Sinorhizobium meliloti and 4 Trichoderma species (T. velutinum, T. tomentosum, T. gamsii and T. harzianum). In an experimental scheme of 4 x 4 strains x species combinations, we investigated the rhizobia physiological and transcriptomic responses elicited by fungal spent media, as well as spent media effects on rhizobia-host legume plant (alfalfa, Medicago sativa L.) symbiosis. Fungal spent media had large effects on rhizobia, specific for each fungal species and rhizobial strains combination, indicating a general rhizobia genotype x fungal genotype interaction. Differential expression of a high number of genes was shown in rhizobia strains. Moreover, changes in rhizobia exopolysaccharide and auxin production were identified in response to fungal spent media. Different rhizobium-fungus combinations were also shown to have synergistic effects on alfalfa symbiotic phenotypes. Our results provide a first insight into interactions involving nitrogen-fixing rhizobia and rhizospheric fungi, highlighting the panoply of genes and genotypic interactions (fungus, rhizobium, host plant) which may concur to plant symbiosis.