This paper focuses on the nationality and citizenship crisis in post-separation Sudan. The paper argues that the unresolved issues in the agreement, especially the issue of nationality and citizenship are serious threats to the stability of the new state of South Sudan. Both North Sudan and South Sudan have demonstrated a lack of political will to resolve the nationality and citizenship problem. This explains why they were not able to adopt a common legal framework that will help to address the age-long problem instead of each adopting new nationality laws. The paper adopts the historical and institutional-legalistic approach in the discourse to situate the problem. It argues therefore, that the citizenship problem will continue in a system that is stratified along ethnic/racial and religious lines as epitomized in Sudan. We conclude that it is the resolution of outstanding issues of nationality and citizenship question that will help to sharpen the pattern of state-ethnic relations in the separated countries of north and south Sudan. With independence granted to Southern Sudan, the crisis of citizenship remains both in the north and the south.