Migration has been a socio-political hallmark in Southeast Asia, more so in recent times as the region advances towards an ASEAN community by 2015. With its steady economic growth and internal political stability, Malaysia receives the most number of migrants aside from Thailand and Singapore. Statelessness and its risk look set to continue in the long run both as a cause and implication of cross-border movement of persons. A considerable number of such migrants share one striking attribute, i.e. their irregular status in the host country, and hence, the lack of protections of their basic rights both from the source and host countries. Going on the premise that there is a strong underexplored nexus between migration and statelessness, this article unravels the interconnections between these two scenarios. Beginning with the crucial introduction of the term 'statelessness' and its causes and consequences, this article subsequently embarks on exploring the manner in which modern patterns of migration expose several groups of vulnerable persons of a migratory background to the risk and limbo of statelessness in Malaysia. Central to then analysis are how the identified groups of persons are impacted by both concepts of de jure and de facto statelessness, the unique interplay between migration and statelessness, the many facets of disenfranchisement of rights saddled upon them by their irregular status, and the underlying challenges behind such anomaly. The article adopts international law as the main framework to guide the overall discussion.