Wheat (Triticum æstivum L.) is an important East Africa highland crop but yields are low. Information is scarce for optimization of fertilizer use. Research was conducted to determine yield response functions for N, P and K, and to diagnose Mg–S–Zn–B deficiencies. The average grain yield increase in Rwanda due to N application was 1.5 Mg ha−1 with a mean economically optimal rate (EOR) of 68 kg ha−1 N. In Kenya and Tanzania, yield was increased by 29% with EOR N for two SY but unaffected by N rate for four other SY which on average had 50% of the soil organic C (SOC) as the N-responsive SY. Yield was increased, on average, with application of P and K by 0.47 and 0.23 Mg ha−1, respectively, at EOR in Rwanda but effects were inconsistent for other SY where soil test K was higher than in Rwanda. Application of Mg–S–Zn–B resulted in 0.46 Mg ha−1 more yield in Rwanda but did not affect yield at other SY where the average soil test values for these nutrients was 35% higher than in Rwanda. If the financially constrained farmer opts to apply the affordable fertilizer to twice as much land at 50% EOR compared with 100% EOR, the mean yield increase is reduced by 27% but production and PCR are increased by 43 and 72%, respectively. Nutrient effects were relatively consistent and positive in Rwanda, but less and less inconsistent elsewhere with generally less SOC, more K–Mg–S–Zn–B availability, and often lower yields.