The Canadian Arctic provides important habitat for millions of marine birds. Some key habitat sites for these have already been protected, but many others lack official protected status and remain vulnerable to various anthropogenic threats. The authors worked with the community of Qikiqtarjuaq, Nunavut, to create two new National Wildlife Areas that protect the colonies, and the nearby marine area, of approximately 500,000 birds during the breeding season. The process has taken two decades to complete, in part due to misunderstanding and mistrust of government on the part of aboriginal residents. In this paper the path that led to the creation of these sites is traced. This has included the approach adopted to collaborating with the local community, incorporating aboriginal (local) ecological knowledge, conducting scientific surveys while building local capacity for further scientific investigation, and finding a solution that addressed the disparate interests of the various stakeholders in this process.