Background: In Australia generally, smoking prevalence more than halved after 1980 and recently commenced to decline among Australia's disadvantaged Indigenous peoples. However, in some remote Indigenous Australian communities in the Northern Territory (NT), extremely high rates of up to 83% have not changed over the past 25 years. The World Health Organisation has called for public health and political leadership to address a global tobacco epidemic. For Indigenous Australians, unprecedented policies aim to overcome disadvantage and close the 'health gap' with reducing tobacco use the top priority. This study identifies challenges and opportunities to implementing these important new tobacco initiatives in remote Indigenous communities. Methods: With little empirical evidence available, we interviewed 82 key stakeholders across the NT representing operational- and management-level service providers, local Indigenous and non-Indigenous participants to identify challenges and opportunities for translating new policies into successful tobacco interventions. Data were analysed using qualitative approaches to identify emergent themes. Results: The 20 emergent themes were classified using counts of occasions each theme occurred in the transcribed data as challenge or opportunity. The 'smoke-free policies' theme occurred most frequently as opportunity but infrequently as challenge while 'health workforce capacity' occurred most frequently as challenge but less frequently as opportunity, suggesting that policy implementation is constrained by lack of a skilled workforce. 'Smoking cessation support' occurred frequently as opportunity but also frequently as challenge suggesting that support for individuals requires additional input and attention. Conclusions: These results from interviews with local and operational-level participants indicate that current tobacco policies in Australia targeting Indigenous smoking are sound and comprehensive. However, for remote Indigenous Australian communities, local and operational-level participants' views point to an 'implementation gap'. Their views should be heard because they are in a position to provide practical recommendations for effective policy implementation faithful to its design, thereby translating sound policy into meaningful action. Some recommendations may also find a place in culturally diverse low- and middle-income countries. Key words: tobacco policy implementation, challenges, opportunities, remote Indigenous Australian communities.