In southern Africa, soil nutrient reserves are being depleted because of continued nutrient mining without adequate replenishment. The consequent downward spiral of soil fertility has led to a corresponding decline in crop yields, food insecurity, food aid and environmental degradation. The central issue for improving agricultural productivity in southern Africa is how to build up and maintain soil fertility despite the low incomes of smallholder farmers and the increasing land and labour constraints they face. Under this review five main options namely: inorganic fertilizers, grain legumes, animal manures, integrated nutrient management and agroforestry options appropriate to smallholder farmers are presented. Issues addressed in the use of inorganic fertilizers are reduction in fertilizer costs, timely availability and use efficiency. Legumes can be used to diversify farm system productivity but this requires P and lime application to support better legume growth and biological nitrogen fixation (BNF) as well as development of markets for various legume products. Manure availability and quality are central issues in increasing smallholder farm productivity and increasing its efficiency through proper handling and application methods. Integrated nutrient management of soil fertility by combined application of both inputs will increase use efficiency of inputs and reduce costs and increase profitability; but the challenge is often how to raise adequate amounts of either inorganic or organic inputs. Issues such as quality of inputs, nutrient balancing, labour to collect and transport organic inputs and their management need to be optimized. These are the challenges of adoption as are the scaling up of these options to millions of small-scale farmers.