Background: To improve Australian Aboriginal and Torres Strait Islander people’s access to, and experience of, healthcare services, including Alcohol and other Drug (AoD) treatment services, principles and frameworks have been developed to optimise cultural responsiveness. Implementing those principles in practice, however, can be difficult to achieve. This study has five aims: i) to describe a five-step process developed to operationalise improvements in culturally responsive practice in AoD services; ii) to evaluate the fidelity of implementation for this five-step process; iii) to identify barriers and enablers to implementation; iv) to assess the feasibility and acceptability of this approach; and v) to describe iterative adaptation of implementation processes based on participant feedback. Methods: Participating services were 15 non-Aboriginal AoD services in New South Wales, Australia. Implementation records were used to assess the implementation fidelity of the project. Structured interviews with chief executive officers or senior management were conducted, and interview data were thematically analysed to identify project acceptability, and the key enablers of, and barriers to, project implementation. Quantitative descriptive analyses were performed on the post-implementation workshop survey data, and responses to the free text questions were thematically analysed. Results: A high level of implementation fidelity was achieved. Key enablers to improving culturally responsive practice were the timing of the introduction of the five-step process, the active interest of staff across a range of seniority and the availability of resources and staff time to identify and implement activities. Key barriers included addressing the unique needs of a range of treatment sub-groups, difficulty adapting activities to different service delivery models, limited time to implement change in this evaluation (three months) and the varied skill level across staff. The project was rated as being highly acceptable and relevant to service CEOs/managers and direct service staff, with planned changes perceived to be achievable and important. Based on CEO/management feedback after the project was implemented at the initial services, several improvements to processes were made. Conclusion: The operationalisation of the five-step process developed to improve cultural responsiveness was feasible and acceptable and may be readily applicable to improving the cultural responsiveness of a wide variety of health and human services.