Statelessness’ is both a legal condition and a social label that sets the parameters of policy discussions and influences broader discourses. Both of these can be seen in the case of the Rohingya who have been displaced from their homes in Myanmar. Many Rohingya who are seeking safe return to their homelands feel their identities and their futures are being negatively impacted by the slow and ongoing production of statelessness in Myanmar, as well as by the label ‘stateless’ that frames understandings of their persecution in international discourses. Both the condition and the labelling process can profoundly affect international approaches to securing the futures of such individuals in Myanmar and beyond. The analysis presented in this chapter is based on narrative research with Rohingya in Bangladesh, Malaysia, and India between 2017 and 2019, including focus groups and in-depth interviews with 100 participants. The chapter considers how Rohingya negotiate, resist, and problematise the labelling process. It explores Rohingya narratives relating to their identity documents and citizenship with a focus on how and why they resist the documents, categories, and labels that frame them domestically and internationally as foreign or stateless. It concludes that the category ‘stateless’, for many affected Rohingya, represents a deficit of protection, justice, and restitution. Until the term becomes better endowed with rights and protections, it will remain contested.