BACKGROUND: The Indigenous Tobacco Control Initiative and Tackling Indigenous Smoking Measure were both announced by the Australian Government at a time when its rhetoric around the importance of evidence-based policy making was strong. This article will (1) examine how the Rudd Government used evidence in Indigenous tobacco control policy making and (2) explore the facilitators of and barriers to the use of evidence. METHODS: Data were collected through: (1) a review of primary documents largely obtained under the Freedom of Information Act 1982 (Commonwealth of Australia) and (2) interviews with senior politicians, senior bureaucrats, government advisors, Indigenous health advocates and academics. Through the Freedom of Information Act process, 24 previously undisclosed government documents relevant to the making of Indigenous tobacco control policies were identified. Interviewees (n=31, response rate 62%) were identified through both purposive and snowball recruitment strategies. The Framework Analysis method was used to analyse documentary and interview data.RESULTS: Government policy design was heavily influenced by recommendations presented in government authored/commissioned literature reviews. Resulting policies were led by equivocal evidence for improved tobacco control outcomes among Indigenous Australians. Many of the cited studies had methodological limitations. In the absence of high quality evidence, some policy makers supported policy recommendations that were perceived to be popular among the Indigenous community. Other policy makers recognised that there were barriers to accumulating rigorous, generalizable evidence; in the absence of such evidence, the policy makers considered that the ‘need for action’ could be combined with the ‘need for research’ by introducing innovative strategies and evaluating them.DISCUSSION: Despite the absence of high quality evidence, the formulation and adoption of Indigenous Tobacco policy was neither irrational nor reckless. The decision to adopt an innovate and evaluate strategy was justifiable given: (a) the potential for the gap between Indigenous and non-Indigenous health outcomes to worsen in the absence of an imminent policy response; (b) the existence of circumstances which made it difficult to obtain high quality evidence to guide policy; and (c) the need for policy solutions to reflect community preferences, given socio-historical sensitivities.