Tobacco-related conditions contribute significantly to the health gap between Indigenous and non-Indigenous Australians. Smoking rates in Australia's Indigenous population has failed to decline even though smoking rates in Australia have declined in general. In some Indigenous communities, smoking rates remain very high. This paper outlines a project to investigate appropriate strategies to assist Indigenous smokers to quit and the important role nurses can play.