Soil nutrient depletion in Uganda is one of the leading environmental degradation problems threatening the livelihoods of most farmers in the region. In order to identify policy options that may be used to address the problem, this study was conducted with an objective of analyzing the determinants of flow and balances of nitrogen (N), Phosphorus (P), and Potassium (K) in Uganda. Data for this study were collected from 58 randomly selected farmers who participated in on-farm fertilizer trials and household surveys conducted in 2000 to 2001. Econometric models were used to analyze the determinants of soil nutrient flows and balances. Only 5% of the sample households had positive total NPK balances implying 95% of the farmers likely used unsustainable land management practices in the 2000/2001 season. If inorganic fertilizer were used to restore the mined nutrients, it would cost an equivalent of a fifth of the farm income. The results confirm the heavy reliance of smallholder farmers to soil fertility mining for their livelihoods. Agricultural potential, size of livestock herd, crop diversity, education, and having non-farm activities improve soil nutrient balances. This implies farmers need to be encouraged to grow crops and keep livestock in order to utilize the crop-livestock synergies. Education and non-farm activities in rural areas also need to be promoted as they contribute to more sustainable land management practices. Contact with extension agents initially accelerates soil nutrient depletion probably due to tendency of farmers to first adopt improved crop varieties without using fertilizer. Hence there is need for extension messages to emphasize adoption of both soil fertility and seed technologies. Farmers in high market access appear to deplete their soils more rapidly, pointing to the need to design policy mechanisms that would reduce soil nutrient depletion in high market access areas.