In remote Aboriginal communities in East Arnhem Land, Northern Territory of Australia, the Yolŋu people, traditional owners of this remote and isolated region, have a long tradition of ŋarali’ [tobacco] use, which is commemorated within funeral ceremony, as manikay [songlines] and buŋgul [dancing]. Today, smoking is very prevalent and a highly normalised social activity among Yolŋu. There are concerns that tobacco control activities aiming to denormalise smoking may lead to stigma in already disadvantaged communities with high smoking prevalence. Interviews were conducted from August 2014 until December 2015 to ascertain whether smokers may have experienced smoking-related stigma through their interactions and engagement with health services and regional tobacco control activities including denormalisation strategy. Informants described their experiences, observations and perceptions of smokefree environments, television and media advertising, and smoking cessation support. We found that while tobacco control denormalisation is not leading to stigma in these communities, some clinical consultations and interactions may have led to feelings of smoking-related shame among Yolŋu health workers who smoked. However, we found that caring, trusting relationships and having the right people communicating the right messages respectfully enabled raising the issue of smoking in clinical consultations without causing shame.