This paper presents the findings from a qualitative study, which sought to investigate the barriers and enablers to implementation of a continuous quality improvement (CQI) program by health-care professionals in Aboriginal primary health-care services in South Australia. Eighteen semi-structured interviews across 11 participating services were conducted alongside CQI implementation activities. Multiple barriers exist, from staff perspectives, which can be categorised according to different levels of the primary health-care system. At the macro level, barriers related to resource constraints (workforce issues) and access to project support (CQI coordinator). At the meso level, barriers related to senior level management and leadership for quality improvement and the level of organisational readiness. At the micro level, knowledge and attitudes of staff (such as resistance to change; lack of awareness of CQI) and lack of team tenure were cited as the main barriers to implementation. Staff identified that successful and sustained implementation of CQI requires both organisational systems and individual behaviour change. Improvements through continuing regional level collaborations and using a systems approach to develop an integrated regional level CQI framework, which includes building organisational and clinic team CQI capacity at the health centre level, are recommended. Ideally, this should be supported at the broader national level with dedicated funding.