This thesis investigates the search for new relationships between indigenous and settler peoples in Australia and Canada. Both reconciliation and the treaty-making process in British Columbia are understood as attempts to build such relationships. Yetthese are policies that have arisen in response to the persistence of indigenous claims for recognition of rights and respect for identity. Consequently, I consider what the purpose of new relationships might be: is the creation of new relationships to be the means by which settlers recognise and respect indigenous rights and identities, or is there some other goal? To answer this, I analyse the two policies as the opening of negotiations over indigenous claims for recognition. That is, the opening of new political spaces in which indigenous people's voices and claims may be heard. Reconciliation opened a space to rethink Australian attitudes to history and culture, to renegotiate Australian identity. Treaties in British Columbia primarily seek to renegotiate ownership and control of lands and resources. Both policies attempt to relegitimise the polities in which they operate, by making new relationships that provide for mutual recognition. However, the thesis establishes that these new spaces are not nearly as expansive or inclusive as they are made out to be. They are in fact defined by the internal struggles of settler society to make life more certain: to resume identities that are secure and satisfying, and to restore territorial control and economic security. This takes place with little regard for the legitimate claims of indigenous peoples to be recognised as people and to enjoy dynamic, flourishing identities of their own. Building new relationships becomes the path to entrenching old certainties.