Protected areas in Australia are of great importance to the tourism industry, conservation agencies, and other stakeholders. Due to an increase in limited resources and the complexity and uncertainty of the protected area/tourism planning context, these stakeholders are encouraged to enter partnerships. Their ability to work together effectively influences the quality of the tourist experience, the satisfaction of visitors, and the protection of the natural resource base on which the industry depends. This paper reports on in-depth interviews undertaken within a wider project that explored a number of different types of partnerships involved in tourism and protected areas with the aim of providing recommendations to policy makers regarding how successful partnerships operate. Seven key themes for policy recommendations emerged. It is suggested that, by considering and acting on these recommendations, policy makers can provide an environment that is more conducive to a collaborative approach for the management of sustainable tourism in protected areas. It is further suggested that the themes arising in this study have the potential for a wider application in a variety of tourism partnership settings.