Complex, transnational issues like the tobacco epidemic are major challenges that defy analysis and management by conventional methods, as are other public health issues, such as those associated with global food distribution and climate change. We examined the evolution of indoor smoke-free regulations, a tobacco control policy innovation, and identified the key attributes of those jurisdictions that successfully pursued this innovation and those that to date have not. In doing so, we employed the actor-network theory, a comprehensive framework for the analysis of fundamental system change. Through our analysis, we identified approaches to help overcome some systemic barriers to the solution of the tobacco problem and comment on other complex transnational problems.