The cultivation of grain legumes (e.g., common bean) in sub-Saharan Africa contributes to the provision of food for a growing population and delivers environmental benefits such as inputs of nitrogen (N) to crops and soil via symbiotic nitrogen fixation (SNF). However, the success of SNF is constrained by several factors such as the poor efficiency of native rhizobial strains to fix N, the low availability of phosphorus (P) and the acidity of soils. Two trials have been conducted in low-fertility tropical soils at the smallholder farm scale in Madagascar to assess the effects of Rhizobium inoculation together with inputs of P and lime on the growth of the common bean. We showed that inoculation with native strains of Rhizobium had significant effects on bean root nodulation, which was increased by up to 15-fold on plant growth, which increased by 78% and on bean yield, which increased by 126%. Moreover, we observed positive and significant relationships between inoculation with Rhizobium and P fertilization on nodulation, plant growth and yield. However, the addition of dolomite lime did not show any effect in our study. The addition of P decreased the mycorrhization rate of roots. Additional research is still needed to improve our understanding of soil fertility conditions (mainly on nutrient availability, including micronutrients) allowing better efficiency of legume symbionts (rhizobium and mycorrhiza) in such low-fertility soils.