The overexploitation of natural resources and the increasing number of social conflicts following from their unsustainable use point to a wide gap between the objectives of sustainability and current resource management practices. One of the reasons for the difficulties to close this gap is that for evolving complex systems like natural and socio-economic systems, sustainability cannot be a static objective. Instead sustainable development is an open evolutionary process of improving the management of social-ecological systems, through better understanding and knowledge. Therefore, natural resource management systems need to be able to deal with different temporal, spatial and social scales, nested hierarchies, irreducible uncertainty, multidimensional interactions and emergent properties. The co-evolutionary perspective outlined in this paper serves as heuristic device to map the interactions settled in the networks between the resource base, social institutions and the behaviour of individual actors. For this purpose we draw on ideas from complex adaptive systems theory, evolutionary theory and evolutionary economics. Finally, we outline a research agenda for a co-evolutionary approach for natural resource management systems.