European Union citizenship was introduced by the Treaty of Maastricht in 1992 and is currently held by approximately 500 million people. In 2001, the European Court of Justice (hereinafter: ECJ or Court) famously held in Grzelczyk that “Union citizenship is destined to be the fundamental status of nationals of the Member States”.1 This article aims to contribute to the ongoing debate regarding the shift in the Court’s case law on EU citizenship,2 by exploring whether EU citizenship can still be considered as the fundamental status of every citizen of the European Union or whether some EU citizens are excluded from this status and the rights associated therewith. This question is discussed against the background of the inherently open notion of integration and against two principles of the Rechtsstaat, one being the principle of legal certainty and the other being the principle of proportionality. The notion of integration and the principle of proportionality share common features as they are open-ended, require an assessment of the facts of the individual case and are therefore not conducive to establishing legal certainty. This article addresses the Court’s recourse to the respective concepts and the effects of the application of these concepts on EU citizenship. It is argued that the Court’s recourse to the principle of legal certainty is used to forego a proportionality assessment. The lack of a proportionality assessment and thereby a lack of an assessment of the facts of the individual case and a balancing process, disadvantages specific groups of EU citizens. In other areas of citizenship law, the Court establishes the requirement of an assessment of the EU citizen’s integration in the host Member State. This approach, however, has the effect of undermining legal certainty and furthers the exclusion of EU citizens from the protection against expulsion or the acquisition of permanent residence status. The ECJ’s recourse to the principle of legal certainty or the concept of integration enhances Member States’ sovereignty, their margin of discretion vis-à-vis EU citizens and weakens the legal position of EU citizens.