Background: The implementation of multidisciplinary stroke rehabilitation interventions is challenging, even when the intervention is evidence-based. Very little is known about the implementation of complex interventions in rehabilitation clinical trials. The aim of study was to better understand how the implementation of a rehabilitation intervention in a clinical trial within acute stroke units is experienced by the staff involved. This qualitative process evaluation was part of a large Phase III stroke rehabilitation trial (AVERT). Methods: A descriptive qualitative approach was used. We purposively sampled 53 allied health and nursing staff from 19 acute stroke units in Australia, New Zealand and Scotland. Semi-structured interviews were conducted by phone, voice-internet, or face to face. Digitally recorded interviews were transcribed and analysed by two researchers using rigorous thematic analysis. Results: Our analysis uncovered ten important themes that provide insight into the challenges of implementing complex new rehabilitation practices within complex care settings, plus factors and strategies that assisted implementation. Themes were grouped into three main categories: staff experience of implementing the trial intervention, barriers to implementation, and overcoming the barriers. Participation in the trial was challenging but had personal rewards and improved teamwork at some sites. Over the years that the trial ran some staff perceived a change in usual care. Barriers to trial implementation at some sites included poor teamwork, inadequate staffing, various organisational barriers, staff attitudes and beliefs, and patient-related barriers. Participants described successful implementation strategies that were built on interdisciplinary teamwork, education and strong leadership to 'get staff on board', and developing different ways of working. Conclusions: The AVERT stroke rehabilitation trial required commitment to deliver an intervention that needed strong collaboration between nurses and physiotherapists and was different to current care models. This qualitative process evaluation contributes unique insights into factors that may be critical to successful trials teams, and as AVERT was a pragmatic trial, success factors to delivering complex intervention in clinical practice. Trial registration: AVERT registered with Australian New Zealand Clinical Trials Registry ACTRN12606000185561.