Citizenship, today, is a concept in crisis. At the international level, migration poses significant questions of justice with regard to citizenship as an exclusionary status;while at the regional and domestic level, citizenship is being challenged by growing nativist politics and arbitrary exercises of naturalisation powers. One site where this crisis can be observed is the citizenship of the European Union (EU). First, Brexit has shown that EU citizenship as an inclusive status beyond nationality is fragile and contingent. Second, arbitrary naturalisation by States according to domestic rules ensures that EU citizenship sufers from the same exclusionary problems as national citizenship. These two problems, I argue, are not the prime vices from which EU citizenship sufers. The biggest faw in the concept of citizenship is found in the absence of citizenship, namely statelessness. By failing to consider the ‘other’, i.e., the problem of statelessness, judgments of the European Court of Justice (ECJ) on citizenship and ‘third-country nationals’ leave this problem unaddressed. Existing academic research has suggested a range of solutions, from harmonising norms on statelessness and acquisition of citizenship (Swider and Den Heijer) to relaxing criteria for naturalisation (Swoboda), decoupling of local, national, and regional citizenship (Bauböck), and establishing EU citizenship as a subsidiary status protecting against statelessness (Kostakopoulou). In this article, I propose to review these solutions and the literature on statelessness in the context of EU citizenship. Choosing EU citizenship as an instance of the broader citizenship crisis, I argue that the framework of international human rights provides a way out by further separating the two facets of citizenship—the political facet of citizenship as identity/nationality and the legal facet of citizenship as a status that enables a person to have rights.