The study investigates the impact of decentralization and local government capacity on efficiency of health service delivery in Uganda applying qualitative analysis, and two stage Data Envelopment Analysis (DEA) on quantitative data covering a sample of 44 districts over the period 2008/09 and 2009/10. The results show that health institutions in about 31 districts out of 44 were technically efficient, while those in about 13 districts were technically inefficient under variable returns to scale (VRS), implying that health resources were not efficiently used in these institutions. Health institutions in 56.8 percent and 45.5 percent of the districts were operating at optimal scale in 2008/09 and 2009/10, respectively. Those in the remaining districts were scale inefficient, with a majority of them operating under decreasing returns to scale (DRS). Effective and accountable decentralized governance in the health sector in Uganda is typically constrained by weak capacity, particularly under-staffing at the districts levels. Policy recommendations include strengthening professional staffing in some districts to improve their capacity to deliver efficient health services; transfers of officials from districts with excess capacity to those with inadequate resources; and districts whose operations are characterized by increasing returns to scale should be considered for future expansion to consolidate their efficiency.