Smallholder agriculture in sub-Saharan Africa provides basis of rural livelihoods and food security, yet farmers have to cope with land constraints, variable rainfall and unstable institutional support. This study integrates a diversity of approaches (household typology and understanding of farm trajectories, on-farm trials, participatory ex-ante trade-off analysis) to design innovative farming systems to confront these challenges. We explored farm trajectories during two decades (1994 to 2010) in the Koutiala district in southern Mali, an area experiencing the land constraints that exert pressure in many other parts of sub-Saharan Africa. We classified farms into four types differing in land and labour productivity and food self-sufficiency status. During the past two decades, 17% of the farms stepped up to a farm type with greater productivity, while 70% of the farms remained in the same type, and only 13% of the farms experienced deteriorating farming conditions. Crop yields did not change significantly over time for any farm type and labour productivity decreased. Together with 132 farmers in the Koutiala district, we tested a range of options for sustainable intensification, including intensification of cereal (maize and sorghum) and legume (groundnut, soyabean and cowpea) sole crops and cereal-legume intercropping over three years and cropping seasons (2012-2014) through on-farm trials. Experiments were located across three soil types that farmers identified – namely black, sandy and gravelly soils. Enhanced agronomic performance was achieved when targeting legumes to a given soil type and/or place in the rotation: the biomass production of the cowpea fodder variety was doubled on black soils compared with gravelly soils and the additive maize/cowpea intercropping option after cotton or maize resulted in no maize grain penalty, and 1.38 t ha-1 more cowpea fodder production compared with sole maize. Farm systems were re-designed together with the farmers involv