Statelessness in Central Asian republics historically stems from the dissolution of the former Soviet Union in 1991, of which they all were a constituent part. Even though these republics had adopted inclusive and gender-neutral citizenship laws in the post-Soviet period, such laws failed to stipulate legal safeguards against hidden statelessness dimensions in the specific regional context of state succession. These laws, coupled with a conflict between formal law and indigenous practices, restoration of traditionalist societal tendencies, and bureaucratic administrative and technical procedures, created numerous stateless persons of undetermined citizenship, including across the border areas. As in many other parts of the world where statelessness exists, in Central Asia, it mostly affected the rights of women and children. Whereas recent policies of each republic positively address the statelessness problem within their own jurisdiction, such individual initiatives do not offer a long-term solution in a wider regional perspective. For state and non-state actors to be more successful in eliminating future incidences of statelessness, they must consider multiple challenges, including the relationship between gender and statelessness, not just within each separate jurisdiction but from a wider Central Asian regional perspective.