The World Health Organization (WHO) Surgical Safety Checklist is a cost-effective tool that has been shown to improve patient safety. We explored the applicability and effectiveness of quality improvement methodology to implement the WHO checklist and surgical counts at Mbarara Regional Referral Hospital in Uganda between October 2012 and September 2013. Compliance rates were evaluated prospectively and monthly structured feedback sessions were held. Checklist and surgical count compliance rates increased from a baseline median (IQR [range]) of 29.5% (0-63.5 [0-67.0]) to 85.0% (82.8-87.5 [79.0-93.0]) and from 25.5% (0-52.5 [0-60.0]) to 83.0% (80.8-85.5 [69.0-89.0]), respectively. The mean all-or-none completion rate of the checklist was 69.3% (SD 7.7, 95% CI [64.8-73.9]). Use of the checklist was associated with performance of surgical counts (p value< 0.001; r(2) = 0.91). Pareto analysis showed that understaffing, malfunctioning and lack of equipment were the main challenges. A carefully designed quality improvement project, including stepwise incremental change and standardisation of practice, can be an effective way of improving clinical practice in low-income settings.