Indigenous political theory offers an important critical resource in developing more nuanced broader understandings of citizenship and thereby also nuanced practice in the area of statelessness. Citizenship of a recognised State is often seen uncritically as the first and most important step in addressing the deprivations experienced as a result of statelessness. This chapter expresses that alongside supporting individuals to access their rights in whichever way necessary, there needs to be a significant re-examination of the liberal theoretical understanding of the State system itself in the light of the claims both of stateless persons and of members of Indigenous Nations. With a focus primarily on North American contexts, the chapter then explores the remedies currently offered for the problems associated with statelessness which are rooted in an assumption of citizenship of a member of the existing community of States as the only way in which people can or should relate politically within a State's territory and internationally.