Range shifts and changes in dominance of species in communities are among the major predicted impacts of climate change on ecosystems, supported by numerous modeling studies. While climate is changing particularly rapidly in the Arctic, little observational data is available to document predicted changes in the composition of communities, in particular from the large Russian tundra areas. Small rodents are a key component of tundra ecosystems implementing important ecological functions both as herbivores and as main prey for a whole guild of predators. Here we document changes over 60 years in occurrence of nine species of small rodents along a latitudinal gradient spanning from the forest-tundra ecotone to the high Arctic tundra on the Yamal Peninsula. All data were obtained using a single method: snap-trapping. In general, the occurrence of lemmings, specialized arctic endemics, decreased in the southern parts of the peninsula, whereas the occurrence of voles, representing boreal or wide-spread species, increased and expanded northwards. The occurrence of Siberian lemmings (Lemmus sibiricus) in particular declined over the whole latitudinal gradient and possibly disappeared from the southernmost zones, whereas collared lemmings (Dicrostonyx torquatus) declined significantly only in the forest tundra. The strongest increase was observed in the tundra zones for narrow-headed voles (Lasiopodomys gregalis), a wide-spread species inhabiting meadows and riparian habitats, and Middendorff’s voles (Alexandromys middendorffii), a primarily low Arctic species inhabiting waterlogged tundra. Both species also expanded their distribution range northwards during the last two decades. The observed changes might be due to the effect of several drivers of environmental change occurring in concert: climate warming both in winter and in summer, and increased human activity notably related to intensive reindeer herding and industrial development.