Legumes (soybeans, peas, lentils, etc.) play important roles in agriculture on Earth because of their food value and their ability to form a mutualistic beneficial association with rhizobia bacteria. In this association, the host plant benefits from atmospheric nitrogen fixation by rhizobia. The presence of nitrogen in the Mars atmosphere offers the possibility to take advantage of this important plant-microbe association. While some studies have shown that Mars soil simulants can support plant growth, none have investigated if these soils can support the legume-rhizobia symbiosis. In this study, we investigated the establishment of the legume-rhizobia symbiosis on different Mars soil simulants (different grades of the Mojave Mars Simulant (MMS)-1: Coarse, Fine, Unsorted, Superfine, and the MMS-2 simulant). We used the model legume, Medicago truncatula, and its symbiotic partners, Sinorhizobium meliloti and Sinorhizobium medicae, in these experiments. Our results show that root nodules could develop on M. truncatula roots when grown on these Mars soil simulants and were comparable to those formed on plants that were grown on sand. We also detected nifH (a reporter gene for nitrogen fixation) expression inside these nodules. Our results indicate that the different Mars soil simulants used in this study can support legume-rhizobia symbiosis. While the average number of lateral roots and nodule numbers were comparable on plants grown on the different soil simulants, total plant mass was higher in plants grown on MMS-2 soil than on MMS-1 soil and its variants. Our results imply that the chemical composition of the simulants is more critical than their grain size for plant mass. Based on these results, we recommend that the MMS-2 Superfine soil simulant is a better fit than the MMS-1 soil and it's variants for future studies. Our findings can serve as an excellent resource for future studies investigating beneficial plant-microbe associations for sustainable agriculture on Mars.