Australia has one of the world's most successful records on tobacco control. The role of public health advocacy in securing public and political support for tobacco control legislation and policy and program support is widely acknowledged and enshrined in World Health Organization policy documents yet is seldom the subject of analysis in the public health policy research literature. Australian public health advocates tend to not work in settings where evaluation and systematic planning are valued. However, their day-to-day strategies reveal considerable method and grounding in framing theory. The nature of media advocacy is explored, with differences between the conceptualization of routine "programmatic" public health interventions and the modus operandi of media advocacy highlighted. Two case studies on securing smoke-free indoor air and banning all tobacco advertising are used to illustrate advocacy strategies that have been used in Australia. Finally, the argument that advocacy should emanate from communities and be driven by them is considered.