Background Remote Aboriginal communities in Australia experience high rates of bacterial sexually transmissible infections (STIs). To control the transmission and decrease the risk of complications, frequent STI testing combined with timely treatment is required, yet significant delays in treatment have been reported. Perceived barriers to timely treatment for asymptomatic patients in remote communities were explored. Methods: A qualitative study was undertaken as part of the STRIVE (STIs in Remote communities, ImproVed and Enhanced primary health care) project; a cluster randomised controlled trial of a sexual health quality improvement program. During 2012, we conducted 36 in-depth interviews with staff in 22 clinics in remote Australia. Results: Participants included registered nurses (72%) and Aboriginal health practitioners (28%). A key barrier to timely treatment was infrequent transportation of specimens to laboratories often hundreds of kilometres away from clinics. Within clinics, there were delays checking and actioning test results, and under-utilisation of systems to recall patients. Participants also described difficulties in physically locating patients due to: (i) high mobility between communities; and (ii) low levels of community knowledge created by high staff turnover. Participants also suggested strategies to overcome some barriers such as dedicated clinical time to follow-up recalls and taking treatment out to patients. Conclusions: Participants identified barriers to timely STI treatment in remote Aboriginal communities, and systems to address some of the barriers. Innovative strategies such as point-of-care testing or increased support for actioning results, coupled with incentives to individual patients to attend for results, may also assist in decreasing the time to treatment.