Nationality is the legal bond between a person and a state that connotes full and equal membership of the political community. Yet, in the practice of states, not everyone who is admitted as a national enjoys the full package of rights attached, nor the same security of status. The phenomenon of inequality among citizens is particularly apparent when examining the question of how protected the legal bond itself is: citizenship by birth is more secure than citizenship acquired otherwise—such as by naturalisation—and mono citizens are less prone to withdrawal of nationality than persons with dual or multiple nationality. As nationality revocation gains new attention from states as a tool to counter terrorism, prompting much political, public and academic debate, the reality that this measure often applies only to particular sub-groups of citizens demands closer scrutiny. This article explores how law and practice on citizenship deprivation is to be evaluated against contemporary standards of international law. While states justify unequal application of citizenship deprivation measures by invoking the duty to avoid statelessness, this article shows that the application of other international standards such as non-discrimination and the prohibition of arbitrary deprivation of nationality calls into question the legitimacy of citizenship stripping as a security instrument. Finally, the article reflects on the broader implications of the current trend towards greater inequality of citizenship status as a reaction to the perceived threat that terrorism poses to the integrity of the state, discussing how the creation of different classes of citizen is in fact likely to have a deeper and more lasting impact on the foundations of liberal democracies.