The spatial and temporal changes of land use, cropping patterns and cattle keeping were assessed for the period 1961–1999 in Kyamtwara division, Bukoba district, Tanzania. The assessment was based on interpreting aerial photographs, surveys and a review of historical statistical data. The area of grassland declined by 40% with a concomitant increase in annual crop fields and forest of 225 and 36%, respectively. The cropping pattern changed from a predominance of banana/coffee/beans to a complex mixed cropping of banana/coffee/beans/maize and root crops in the homegarden, and increased cultivation of maize and root crops in pure stands. Farmers stopped cultivating sorghum and finger millet. The population of indigenous cattle decreased by 50% and an equal percentage of dairy cattle was introduced, but cattle-owning households decreased by 85%. Nutrient balances of homegardens ranged between -27 and 17 kg N ha-1 yr-1, -1 and 7 kg P ha-1 yr-1 and -5 and 12 kg K ha-1 yr-1, with the positive balances achieved by resource-rich households. Nutrient balances of crops in pure stand ranged between -15 and -2 kg N ha-1 yr-1, -2 and -1 kg P ha-1 yr-1 and -14 and -1 kg K ha-1 yr-1, with more negative balances observed with maize, implying that soil nutrient stocks are decreasing. Increasing population density, coupled with an unequal distribution of resources among households, land tenure, economic policies and poor crop markets were identified as major causal factors of the above changes. Reversing soil fertility decline requires external inputs of nutrients. Within the current poor economic situation of the farming community, different potential soil fertility improvement strategies, including exploitation of N2-fixing legumes are discussed.