As wheat demand is increasing in sub-Saharan Africa (SSA), domestic production is being encouraged. The potential to increase the productivity and profitability of wheat appears large in the region, but little is known about the concrete interventions needed to meet that potential. In this study, we selected a site in Northern Rwanda (representative of the cool humid climatic zone which accounts for most of the spring wheat production of SSA) and analysed the determinants of wheat productivity and profitability for 130 smallholder farms during two consecutive short rainy seasons, namely 2017A and 2018A (wheat is seldom grown during long rainy seasons; potato is the preferred crop then). Although wheat yields were found to be high when compared to typical yields in SSA (means of 3469 and 3052 kg/ha during the seasons 2017A and 2018A, respectively), large yield gaps were also found (1.977 t/ha on average, or 37.6% of the highest farmer’s yield, defined as the average actual yields above the 90th percentile of this variable). Evidences presented in the paper suggest that wheat productivity could be increased through increased seeding rate (a 0.14% increase in wheat grain yield was found with a 1% increase in seeding rate), increased nitrogen (N) application combined with frequent weeding (a 0.02% increase in wheat grain yield was found with a 1% increase in N application and frequent weeding), and labour-saving technologies (e.g., herbicides and mechanization). If wheat profitability would also increase with frequent weeding and labour-saving technologies, it would decrease with increased input use in many cases. Indeed, seed, fertilizer and amendments represent most of the wheat production cost in the area. These results illustrate the importance of assessing the impact of narrowing the yield gap on profitability, not only productivity, as some yield-increasing technologies may not be desirable from an economic perspective. They also demonstrate that resource-saving technologies (input-saving e.g., precision agriculture, labour-saving e.g., mechanization) may be as much in demand by African smallholders as yield-increasing technologies, calling for a more balanced approach in current research and development initiatives on the continent.