This paper presents results of an analysis of potentially harmful elements (PHEs, Pb, Zn and Cu) and conservative element (CE, Fe) concentrations in urban surface deposited sediment (USDS). The study was conducted in seven large Russian cities located in different geographic and climatic zones, and in territories with different geology and anthropogenic pressures: Chelyabinsk, Magnitogorsk, Nizhniy Novgorod, Nizhniy Tagil, Rostov-on-Don, Tyumen, and Ufa. The initial geochemical baseline relationships between PHEs and CE concentrations in the USDS were reconstructed for each city applying an approach based on linear weighted fitting of PHE as a function of CE with lower weights assigned to more polluted samples. The reconstructed average initial baseline Pb, Cu, and Zn concentrations varied between 17-52, 25-196, and 91-413 mg kg, respectively. Several new criteria for assessing the degree of geochemical transformation and pollution of the urban environment, such as the percentage of polluted samples, average pollutant concentration in polluted samples, and weighting degree index δ, were suggested and compared with common criteria, such as the PHE concentration and the geo-accumulation index. The environmental rank of a city significantly differed depending on whether the criterion for ranking was total PHE pollution or changes in comparison with the initial geochemical baseline.