Tobacco smoking is a major health issue for Indigenous Australians, however there are few interventions with demonstrated efficacy in this population. The Transtheoretical Model may provide a useful framework for describing smoking behaviour and assessing readiness to quit, with the aim of developing better interventions. Interviews were conducted with 593 Indigenous Australians in eight rural and remote communities in north Queensland, to examine stages of change and smoking behaviour. Among current smokers, 39.6% and 43.4% were in Precontemplation and Contemplation stages respectively. A further 13.9% were making preparations to quit (Preparation) whilst only 3.2% said they were actively trying to quit (Action). When analysed by stage of change, the pattern of smoking-related behaviours conformed to the results of past research using the model. Importantly however, distribution of individuals across the stages opposes those observed in investigations of smoking behaviour in non-Indigenous Australian populations. The Transtheoretical Model can be used to meaningfully classify Indigenous smokers in remote north Queensland according to stages along the behaviour change continuum. Importantly, in this large sample across eight communities, most Indigenous smokers were not making preparations to change their smoking behaviour. This suggests that interventions should focus on promoting movement toward the Preparation and Action stages of change.