This study analyzes the problem of nationality and residency in Morocco, Algeria, Tunisia and Mauritania by deconstructing legislation and policies related to residency and nationality in these countries. Using an approach that combines descriptive legal methodology and comparative research, this study investigates their peculiarities, intersections, and similarities, and identifies their strengths and weaknesses. This investigation reveals an important point of comparison at the level of legislation related to entry and residence as legislation was being developed, whether domestically through the adoption of laws governing security and economic concerns, or externally in terms of the ratification of some relevant international agreements. The exception is Tunisia, which remains reluctant to ratify the International Convention on the Protection of the Rights of All Migrant Workers and Members of Their Families. With regard to nationality, the legal frameworks in the four countries remain relatively similar in terms of criteria and procedures for naturalization and are influenced by remarkably similar factors with regard to equality in nationality.