This paper describes the applicability of the Consolidated Framework for Implementation Research (CFIR) to the qualitative evaluation of the implementation of the Queensland Aboriginal and Torres Strait Islander Brief Intervention Training Program, the B.strong Program. Interviews were conducted with 20 B.strong Program trainees and four health service managers from eight purposively sampled Indigenous primary health care services in Queensland to collect their perceptions of the B.strong Program implementation. The 26 constructs of the CFIR were used to guide data collection and analysis. Additional constructs were developed for two program implementation aspects, “quality improvement” and “cultural suitability.” Findings are presented from the application of the CFIR to the evaluation of the implementation of a brief intervention training program in the Australian Indigenous context. While demonstrating the applicability of the CFIR in this evaluation, this study also highlights that it may require modification, to ensure identification of the different contextual factors that influence program implementation.