Smallholder farming systems in sub-Saharan Africa have undergone changes in land use, productivity and sustainability. Understanding of the drivers that have led to changes in land use in these systems and factors that influence the systems’ sustainability is useful to guide appropriate targeting of intervention strategies for improvement. We studied low input Teso farming systems in eastern Uganda from 1960 to 2001 in a place-based analysis combined with a comparative analysis of similar low input systems in southern Mali. This study showed that policy-institutional factors next to population growth have driven land use changes in the Teso systems, and that nutrient balances of farm households are useful indicators to identify their sustainability. During the period of analysis, the fraction of land under cultivation increased from 46 to 78%, and communal grazing lands nearly completely disappeared. Cropping diversified over time; cassava overtook cotton and millet in importance, and rice emerged as an alternative cash crop. Impacts of political instability, such as the collapse of cotton marketing and land management institutions, of communal labour arrangements and aggravation of cattle rustling were linked to the changes. Crop productivity in the farming systems is poor and nutrient balances differed between farm types. Balances of N, P and K were all positive for larger farms (LF) that had more cattle and derived a larger proportion of their income from off-farm activities, whereas on the medium farms (MF), small farms with cattle (SF1) and without cattle (SF2) balances were mostly negative. Sustainability of the farming system is driven by livestock, crop production, labour and access to off-farm income. Building private public partnerships around market-oriented crops can be an entry point for encouraging investment in use of external nutrient inputs to boost productivity in such African farming systems. However, intervention strategies should recognise the diversity and heterogeneity between farms to ensure efficient use of these external inputs.