Common bean and soybean yield poorly on smallholder farms in Rwanda. We evaluated the benefits of inoculation combined with P fertilizer and manure on yields of common bean and soybean in three agro-ecological zones (AEZs), and their residual effects on a subsequent maize crop. In the first season, the treatments included inoculum, three rates of manure, and two rates of P fertilizer, with nine replications (three per AEZ). Both legumes responded well to inoculation if applied together with manure and P fertilizer. Grain yields varied from 1.0 t ha−1 to 1.7 t ha−1 in unamended control plots to 4.8 t ha−1 for common bean and 3.8 t ha−1 for soybean in inoculated plots with both P and manure addition. The response of common bean and soybean to inputs varied greatly between AEZs. In the AEZ with low and erratic rainfall (Bugesera), yields of both legumes and maize were low and maize after soybean failed to yield any grain due to drought. In this regard, early maturing legume varieties are advised in regions of low rainfall. Responses of maize to an input applied to the legumes strongly increased when other inputs were applied together to the legume. This allowed greater maize yields which ranged from 0.8 t ha−1 in control plots to 6.5 t ha−1 in treatments previously inoculated with P and manure added for maize grown after common bean and from 1.9 t ha−1 in control plots to 5.3 t ha−1 for maize grown after soybean. The amount of N2-fixed measured using the 15N-natural abundance method differed between the two legumes and varied between 15 and 198 kg N2 ha−1 for common bean and between 15 and 186 kg N2 ha−1 for soybean and differed enormously among treatments and AEZs. Application of inputs to the legumes also resulted in enhanced N and P uptake of the subsequent maize. The use of inoculum combined with manure and P fertilizer is a good option for smallholder farmers growing common bean and soybean in rotation with maize. We observed strong effects of environment and call for care when targeting crops and technologies for sustainable crop production.