Urban ecological restoration typically employs western science approaches to restore degraded ecosystems. As yet, few restoration groups acknowledge the history of these degraded urban sites, despite connections, past and present, that root Indigenous Peoples (and others) in these lands. Here, we promote partnership with Indigenous communities from project inception and present two successful case studies from Aotearoa New Zealand. We specifically note that partnering and building relationships with Indigenous communities in restoration efforts require recognition of power inequalities and injustices. We consider success to include both restoration of ecological function and biodiversity and reconnection of all communities to urban ecosystems.