Slum upgrading efforts in Kenya got a boost with the inauguration of Kenya slum upgrading programme (KENSUP) in 2003. This is a collaborative initiative between the government of Kenya and UNHABITAT who work together with a variety of other partners to address the problem of slums. Further indication of serious focus on the problem of informal settlements in Kenya has been indicated by another World Bank sponsored Kenya informal settlement improvement programme (KISIP). While all this may excite hope in the over 1.4 million slum dwellers in Nairobi with the big promise for improvement in their living conditions, the implementation process seem to be bedeviled with myriad obstacles that may not be easy to surmount. Some of the most obvious obstacles include lack of space for decanting, high population densities, absolute poverty and resistance from structure owners commonly called slumlords. This paper is going look into some of land related challenges facing slum upgrading efforts in Kenya. The study utilizes information from previous experiences with slum upgrading to illustrate some of the land related factors that have constrained the achievement of anticipated results in the slum upgrading programmes. This is a desktop study that utilizes literature review, government reports and documents and NGO studies to point out pertinent land related obstacles to slum upgrading process in Nairobi.