Objective: To analyse the strategies used by hospital leaders to improve compliance with the 'ensuring correct patient, correct site and correct procedure protocol'. While following such a protocol saves lives according to an international study of the World Health Organization safe surgery checklist, promoting compliance in hospitals has proved to be a regulatory challenge. Design, Setting and Participants: Using a qualitative research design and 'responsive regulation' theory, this study explored implementation strategies used by hospital leaders in 20 Australian public hospitals. Semi-structured interviews were conducted with 72 informants to analyse how front-line leaders improved compliance with the safe surgery protocol in their hospitals. Interventions: Implementation analysis of the safe surgery protocol. Main Outcome Measures: The use of implementation strategies located on a 'responsive regulation' pyramid. Results: Informants identified many strategies used to improve protocol compliance typically beginning with persuasion. Supportive strategies were located on a regulatory pyramid beginning with softer interventions: persuade, enlist leaders, train, remind, relax protocol requirements, redesign hospital systems and reward compliance. In response to low and slow compliance, many hospital leaders switched to a pyramid of escalating sanctions: direct, delegate, monitor, publicly report, reprimand and penalize. Conclusions: A multiplex problem requires graduated and multiplex regulation. Hospital leaders proved to be responsive regulators in applying both multiple supports and sanctions that improved compliance over 3 years. These experiences with protocol implementation illustrate the multifaceted challenge of health sector regulation and offer lessons for embedding future patient safety solutions.