This article traces the historical relationship between Nairobi's city authorities and its informal transport providers, the infamous matatu operators. These conflicts were concentrated at matatu stations, prominent arenas for negotiations over access to infrastructure and the production of urban space. The article argues that the spatial layout of these stations needs to be viewed in the context of a neoliberal restructuring of the city. Neoliberalism is understood here as an economic and political strategy used by state and nonstate actors to differing degrees in different historical conjunctures and played out in urban spaces. The structure of the matatu network is not a result of neglect or self-organization, but rather a complex dynamic, intertwined among many connections between informal and formal modes of social and economic agency and differences in the interests of actors at different levels of the informal hierarchy.