Background: Chlamydia, gonorrhoea and syphilis are readily treatable sexually transmitted infections (STIs) which continue to occur at high rates in Australia, particularly among Aboriginal Australians. This study aimed to: explore the extent of variation in delivery of recommended STI screening investigations and counselling within Aboriginal primary health care (PHC) centres; identify the factors associated with variation in screening practices; and determine if provision of STI testing and counselling increased with participation in continuous quality improvement (CQI). Methods: Preventive health audits (n = 16,086) were conducted at 137 Aboriginal PHC centres participating in the Audit and Best Practice for Chronic Disease Program, 2005-2014. STI testing and counselling data were analysed to determine levels of variation in chlamydia, syphilis and gonorrhoea testing and sexual health discussions. Multilevel logistic regression was used to determine factors associated with higher levels of STI-related service delivery and to quantify variation attributable to health centre and client characteristics. Results: Significant variation in STI testing and counselling exists among Aboriginal PHC centres with health centre factors accounting for 43% of variation between health centres and jurisdictions. Health centre factors independently associated with higher levels of STI testing and counselling included provision of an adult health check (odds ratio (OR) 3.40; 95% Confidence Interval (CI) 3.07-3.77) and having conducted 1-2 cycles of CQI (OR 1.34; 95% CI 1.16-1.55). Client factors associated with higher levels of STI testing and counselling were being female (OR 1.45; 95% CI 1.33-1.57), Aboriginal (OR 1.46; 95% CI 1.15-1.84) and aged 20-24 years (OR 3.84; 95% CI 3.07-4.80). For females, having a Pap smear test was also associated with STI testing and counselling (OR 4.39; 95% CI 3.84-5.03). There was no clear association between CQI experience beyond two CQI cycles and higher levels of documented delivery of STI testing and counselling services. Conclusions: A number of Aboriginal PHC centres are achieving high rates of STI testing and counselling, while a significant number are not. STI-related service delivery could be substantially improved through focussed efforts to support health centres with relatively lower documented evidence of adherence to best practice guidelines.