Kenya attained independence from the British in 1963 and immediately following this, the country embarked on a decolonisation process in the political, social, and economic sectors. As a result of this process, urban landscape symbols began to change. In this paper, we examine how decolonisation occurred through the naming and renaming of streets. Using critical toponymic theory, we analyse the socio-political processes that influenced the inscription of street names as part of the symbolic production of the urban space of Nairobi. Our study suggests that, during the period of British rule (1895–1963), toponymy was used as an exercise of power and ideological dominance over space with the purpose of reflecting British control. Soon after Kenya gained independence, the erasure and re-inscription of street names were used to renounce the colonial regime and its ideology, and redefine the city’s identity with toponymic symbols of nationalism and pan-Africanism. In the process, street names acted as sites for the restitution of justice and arenas for reputational politics, spatial scales of memory, and symbols of ethnic diversity and unity. This research demonstrates the role played by street names as symbols of memory and socio-political ideology, especially during major political transitions.