Faced with the paradox of a large global increase in conservation reserves and a simultaneous global decrease in actual effective protection for biodiversity, conservation scientists and policymakers are questioning established conservation theory and practice. I argue that the fundamental premises, the foundational myths, for Western-style conservation also need to be questioned. The statistics on Indigenous land claims, and conservation reserves, in Australia and more specifically the state of New South Wales (NSW), reveal a landscape of policy failure in both arenas. Focusing on Australia, I use spatial analysis and policy histories to demonstrate converging trajectories of land use priorities for conservation needs and Indigenous peoples’ needs. This intersection, while generating much potential for conflict, also creates new political landscapes. A combination of spatial and cultural analyses can create a clear picture of new “operational landscapes”, and an understanding of the (sometimes) complementary values of different cultural groups negotiating about these landscapes. From the basis that environmental problems are fundamentally social problems, this paper contributes to explorations of new paradigms supporting new social-ecological relationships, and new relationships between Indigenous and non-Indigenous peoples.