The prevalence rate of tobacco smoking remains high for Australian Indigenous people despite declining rates in other Australian populations. Given many Indigenous Australians continue to experience a range of social and economic structural problems, stress could be a significant contributing factor to preventing smoking abstinence. The reasons why some Indigenous people have remained resilient to stressful adverse conditions, and not rely on smoking to cope as a consequence, may provide important insights and lessons for health promotion policy and practice. In-depth interviews were employed to collect oral histories from 31 Indigenous adults who live in metropolitan Adelaide. Participants were recruited according to smoking status (non-smokers were compared with current smokers to gain a greater depth of understanding of how some participants have abstained from smoking). Perceived levels of stress were associated with encouraging smoking behaviour. Many participants reported having different stresses compared with non-Indigenous Australians, with some participants reporting having additional stressors such as constantly experiencing racism. Resilience often occurred when participants reported drawing upon internal psychological assets such as being motivated to quit and where external social support was available. These findings are discussed in relation to a recently developed psycho-social interactive model of resilience, and how this resilience model can be improved regarding the historical and cultural context of Indigenous Australians' experience of smoking.