Using the example of four capital cities of the North Caucasus federal district (Grozny, Magas, Nalchik and Vladikavkaz), this paper examines specifics of symbolic transformation of urban toponymy in the post-Soviet period. A city map is interpreted as a product of construction, that of struggle and one of power instruments. Drawing on the concepts of symbolic domination and places of memory, the author reveals the sense of toponymic redistribution throughout the urban space of the capitals in North Caucasus. Given social and cultural decentralization and deunification of all-Russian space, the areas are searching for their own ways in construction of identity symbols. The author assumes that the capitals of the North Caucasus federal district are the centers in which decisions about the toponymic redistribution are made. In these centers, elites and influence groups develop ideology and policy of national (ethno-cultural) identity and memory. The post-Soviet wave of renaming is directly linked to the disintegration of the Soviet matrix of urbononyms and the revitalization of the de-Sovietization process from the early 1990-s and mid 2000-s. The author believes that today Grozny is one of the leading and specific areas of symbolic transformation of the urban reality in Russia. There is a definite link between changes in urban toponymy and a model of a new Chechen identity. Grozny is systematically losing the symbols of the Soviet and communist identity. From the toponymic perspective, Grozny’s current symbolic space is a symbiosis of several symbols: 1) the Vainakh’s ethno-cultural memorial symbols – secular and religious, 2) Caucasian toponyms, ethnonyms and urbononyms, 3) all-Russian symbols reflecting the cultural legacy of the past and 4) current Russian political and military symbols. The paper includes a table showing key changes in Grozny’s urbononyms. Magas is the capital of Ingushetia, the youngest city in North Caucasus. In Magas, name construction goes along four types of meaning. These types include: 1) international (Eurasian) meaning, 2) federal meaning, 3) North Caucasian meaning and 4) local (Ingush) meaning. In contrast to Grozny, ethno-cultural and secular symbols dominate in Magas urbononyms. The toponymic redistribution in Nalchik – the capital of Kabardino-Balkaria – evolves towards the legitimation and domination of localism, ethno-culturalism and neo-tribalism. The city is gradually losing the names having international and all-Russian meanings. Old Soviet urbononyms are retained in an enclave-like manner. In Vladikavkaz, the capital of North Ossetia-Alania, name construction has following features: 1) the toponymic restoration of urbononyms and 2) the toponymic redistribution linked to the construction of Alanian identity. The author believes that the era of symbolic domination of the Soviet ideology and technology of urban space appropriation is ending. The federal toponymic matrix is leaving urban spaces and being replaced by the local secular and religious (Islamic) urbononyms. This process forms a new model of symbolic reality in the capital cities in North Caucasus.