Australia has over 100,000 rock art sites, with hundreds open for public visitation and dozens of undocumented sites found across the country each year. Consisting of rock shelters, caves, rock platforms and boulders, these are landscape places marked with paintings, drawings, stencils, prints, petroglyphs, finger flutings and figures made of beeswax. For Indigenous Australians, rock art sites are an integral part of living culture and are described as Indigenous history books, libraries, galleries and living museums that are fundamental for the well-being of both individuals and communities. But they are more than heritage places and places of history because they are charged with old and new stories, ancestral connections and social meaning. They are places of knowledge, spirituality and experience that shape Indigenous identity. However, some sites can be shared through actual and/or virtual tourism, connecting people, places and cultures. In this paper it is argued that the best way to protect rock art sites is to take a collaborative landscape approach that addresses the specific needs and concerns of relevant Indigenous communities and Traditional Owners. These needs and concerns vary widely across Australia. Consequently, although broad strategies can be developed, they need to be flexible so as to incorporate local Indigenous knowledge and desires. Case studies and recent research with dozens of New South Wales, Queensland and the Northern Territory communities will structure the paper. It is concluded that the most successful and meaningful way to conserve rock art for future generations is for rock art specialists and community members to work together using both traditional and scientific knowledge, what some refer to as a two toolbox, side-by-side or walking together approach.