Background: Tobacco smoking is the leading contributor to the burden of disease among Aboriginal and Torres Strait Islander Australians. Reducing tobacco use in this population is a public health priority. Precise monitoring of smoking prevalence trends is central to implementation and evaluation of effective tobacco control. The way in which trends are reported influences understanding of the extent of progress, with potential implications for policy. Our objective was to quantify absolute changes in Aboriginal and Torres Strait Islander adult (≥18 years old) daily tobacco smoking prevalence from 2004 to 2015, including comparisons with the total Australian population, and by age, sex and remoteness. Methods: We analysed multiple nationally representative surveys of the Aboriginal and Torres Strait Islander, and total Australian, population conducted from 2004 to 2015. Aligned with strength-based approaches, we applied a progress frame, focusing on absolute differences in smoking prevalence within the Aboriginal and Torres Strait Islander population. Results: The prevalence of current daily smoking among Aboriginal and Torres Strait Islander adults nationally was 50.0% (95% confidence interval [CI] 47.9, 52.2) in 2004-05 and 41.4% (95% CI 39.1, 43.6) in 2014-15, representing an absolute prevalence decrease of 8.6 percentage points (95% CI 5.5, 11.8) over the past decade. This is comparable with the 6.8 percentage point (95% CI 5.6, 7.9) decrease in smoking prevalence in the total Australian population over the same period, from 21.3% in 2004-05 (95% CI 20.5, 22.0) to 14.5% in 2014-15 (95% CI 13.6, 15.4). Particular success in reducing Aboriginal and Torres Strait Islander daily smoking was observed among younger age groups, with a decrease of 13.2 percentage points for 18-24-year-olds (95% CI 5.9, 20.4), 9.0 percentage points for 25-34-year-olds (95% CI 2.7, 15.3) and 8.7 percentage points for 35-44-year-olds (95% CI 2.6, 14.8). Smoking prevalence in those living in urban/regional areas decreased by 10.2 percentage points (95% CI 6.2, 14.1). Conclusions: Substantial progress has been made in reducing smoking, with an estimated 35 000 fewer Aboriginal and Torres Strait Islander adults smoking every day in 2014-15 compared with if daily smoking remained at 2004-05 prevalence. This will lead to thousands of lives saved. The observed success in the younger age groups is encouraging. Continued resourcing and comprehensive tobacco control efforts are required to ensure positive trends continue.