Aim NetworkZ is a simulation-based multidisciplinary team-training programme designed to enhance patient safety by improving communication and teamwork in operating theatres (OTs). In partnership with the Accident Compensation Corporation, its implementation across New Zealand (NZ) began in 2017. Our aim was to explore the experiences of staff - including the challenges they faced - in implementing NetworkZ in NZ hospitals, so that we could improve the processes necessary for subsequent implementation. Method We interviewed staff from five hospitals involved in the initial implementation of NetworkZ, using the Organising for Quality model as the framework for analysis. This model describes embedding successful quality improvement as a process of overcoming six universal challenges: structure, infrastructure, politics, culture, motivation and learning. Results Thirty-one people participated. Structural support within the hospital was considered essential to maintain staff enthusiasm, momentum and to embed the programme. The multidisciplinary, simulation-based approach to team training was deemed a fundamental infrastructure for learning, with participants especially valuing the realistic in situ simulations and educational support. Participants reported positive changes to the OT culture as a result of NetworkZ and this realisation motivated its implementation. In sites with good structural support, NetworkZ implementation proceeded quickly and participants reported rapid cultural change towards improved teamwork and communication in their OTs. Conclusion Implementation challenges exist and strategies to overcome these are informing future implementation of NetworkZ. Embedding the programme as business as usual across a nation requires significant and sustained support at all levels. However, the potential gains in patient safety and workplace culture from widespread multidisciplinary team training are substantial. Trial registration number ACTRN12617000017325.