Recent political turmoil has focused international attention on Egypt, yet there is little awareness of the country’s stateless populations—those who lack legal nationality to any state—or the challenges they face. Individuals in situations of protracted statelessness are denied their right to a nationality, resulting in an array of additional rights violations. Such violations include denied freedom of movement, equality before the law, and access to economic and social rights. Drawing from two years’ of fieldwork data, this study highlights the plight of those who are unable to achieve legal status in a country with harsh punishments for illegal presence, entry, and exit. It also evaluates potential solutions for eliminating statelessness in Egypt and protecting the rights of stateless populations. As Egypt seeks to move beyond revolution, it is vital that the government addresses the pervasive and systemic inequalities that deny individuals their right to a nationality.