Collaborative problem solving has increasingly become important in the face of the complexities in the management of resources, including protected areas. The strategy undertaken by Girringun Aboriginal Corporation in north tropical Queensland, Australia, for developing co-management demonstrates the potential for a problem solving approach involving sequential initiatives, as an alternative to the more familiar negotiated agreements for co-management. Our longitudinal case study focuses on the development of indigenous ranger units as a strategic mechanism for the involvement of traditional owners in managing their country in collaboration with government and other interested parties. This was followed by Australia's first traditional use of marine resources agreement, and development of a multi-jurisdictional, land to sea, indigenous protected area. In using a relationship building approach to develop regional scale co-management, Girringun has been strengthening its capabilities as collaborator and regional service provider, thus, bringing customary decision-making structures into play to 'care for country'. From this evolving process we have identified the key components of a relationship building strategy, 'the pillars of co-management'. This approach includes learning-by-doing, the building of respect and rapport, sorting out responsibilities, practical engagement, and capacity-building.