The problems and challenges of rapidly increasing world population, global climate change, shortages of water suitable for irrigation and degradation of agricultural land are increasing the demand to improve grain production from rainfed arable lands. Specific challenges include estimating the size and thus the value of the yield gap, identifying the factors limiting current average production and designing profitable remedial strategies for a range of agro-ecological regions. This review of the rainfall-limited potential yields and the gap between actual or average yields of cereal and legume crops and the rainfall-limited potential indicates that there is still substantial room to increase the average yield of crops in rainfed systems in both developed and developing regions. The review has indicated that (1) the size of the gap between average and potential yields varies according to the agro-ecological zone and the available technologies from about 0.5 to over 5 t/ha, leaving considerable scope for future yield improvement; (2) there is relatively less information applicable at the farm or field scale that assesses the spatial and temporal variability of the yield gap, the reasons for the gap and the possible methods to close the gap; (3) there is also limited information on the feasibility and profitability of applying various approaches to close the gap, including tactical and strategic management practices and plant breeding; (4) the evidence of the impact of the components of conservation agriculture on crop yields in a wide range of agro-ecological regions supports the adoption of zero tillage and crop rotation but is less clear in support of residue retention; (5) objective identification and testing of factors that limit production can lead to a rational sequence of amelioration that is specific to each agro-ecological or field situation and can close the yield gap in winter-dominant rainfall environments; and (6) farmer-participatory varietal selection, including breeding for specific adaptation can make a substantial contribution to closing the gap in a range of environments. A common observation from the reports reviewed here is that sustainable yield improvement will need to employ a range of methods that are appropriate to specific agro-ecological conditions—previous approaches based on single inputs, practices or genotypes can only be partial solutions.