Sub-national estimates of under-5 mortality are useful for evaluating within-country inequality, tracking progress, and identifying areas of greatest need. We estimate under-5 mortality for each of Zambia’s 72 districts annually 1980-2010, using summary birth history data from censuses and complete birth history data from Demographic and Health surveys to fit a series of small are models. We consider a variety of generalized linear mixed models that differ in how spatial trends, temporal trends, and spatial-temporal interactions are introduced. All models suggest considerable heterogeneity in levels of under-5 mortality, with the worst off districts experiencing mortality risks 2-3 times as great as those in the best off districts. Distinct spatial trends are also apparent: districts in the northeast and southwest experience noticeably higher mortality than districts in the central part of the country. Progress in decreasing mortality over the past 30 years has also been variable: while there is some evidence of decline in most districts, our models suggest that a subset of districts have experienced decreases in mortality exceeding 50%.