This chapter examines the relationship among ungoverned spaces, statelessness and security in Kenya. Statelessness is perceived as a political outcome of the relationship among politics, security and space. It explores the way in which statelessness is examined not from a legal perspective but a spatial-political dimension. The chapter also examines the legal and administrative state of statelessness in Kenya and provides essential information in order to understand how statelessness is examined in the context of ungoverned spaces. It outlines the structural and physical conditions of ungoverned spaces in Kenya. Qualitative research was adopted in this case study that focused on ungoverned spaces. The primary and secondary data used was derived from printed material. The chapter offers recommendations on how states can address the reality of statelessness to transform its adverse implications, both for the State and for the individual stateless persons, into beneficial ones.