Introduction Surgical services are increasingly seen to reduce death and disability in Sub-Saharan Africa, where hospital-based mortality remains alarmingly high. This study explores two implementation approaches to improve the quality of perioperative care in a Tanzanian hospital. Effects were compared to a control group of two other hospitals in the region without intervention. Methods All hospitals conducted quality assessments with a Hospital Performance Assessment Tool. Changes in immediate outcome indicators after one and two years were compared to final outcome indicators such as Anaesthetic Complication Rate and Surgical Case Fatality Rate. Results Immediate outcome indicators for Preoperative Care in the intervention hospital improved (52.5% in 2009; 84.2% in 2011, p<0.001). Postoperative Inpatient Care initially improved to then decline again (63.3% in 2009; 70% in 2010; 58.6% in 2011). In the control group, preoperative care declined from 50.8% (2009) to 32.8% (2011, p <0.001), while postoperative care did not significantly change. Anaesthetic Complication Rate in the intervention hospital declined (1.89% before intervention; 0.96% after intervention, p = 0.006). Surgical Case Fatality Rate in the intervention hospital declined from 5.67% before intervention to 2.93% after intervention (p<0.0010). Surgical Case Fatality Rate in the control group was 4% before intervention and 3.8% after intervention (p = 0.411). Anaesthetic Complication Rate in the control group was not available. Discussion Immediate outcome indicators initially improved, while at the same time final outcome declined (Surgical Case Fatality, Anaesthetic Complication Rate). Compared to the control group, final outcome improved more in the intervention hospital, although the effect was not significant over the whole study period. Documentation of final outcome indicators seemed inconsistent. Immediate outcome indicators seem more helpful to steer the Continuous Quality Improvement program. Conclusion Specific interventions as part of Continuous Quality Improvement might lead to sustainable improvement of the quality of care, if embedded in a multi-faceted approach.