Birth history data—the primary source of data on under-5 mortality in developing countries—are infrequently used for subnational estimates due to concerns over small sample sizes. In this study we consider different methods for analyzing birth history data in combination with various small area models. We construct a simulation environment to assess the performance of different combinations of birth history methods and small area models in terms of bias, efficiency, and coverage. We find that performance is highly dependent on the birth history method applied and how temporal trends are accounted for. We estimated trends in district-level under-5 mortality in Zambia from 1980 to 2010 using the best-performing model. We find that under-5 mortality is highly variable within Zambia: there was a 1.8-fold difference between the lowest and highest levels in 2010, and declines over the period 1980 to 2010 ranged from less than 5% to more than 50%.