The grey-sided vole (Myodes rufocanus) is one of the keystone vole species for ecosystem functioning in boreal forests. In 1970-2008 there has been a long-term decline in the numbers of grey-sided voles within a 100×100 km2 study area in northern Sweden. Habitat destruction is regarded as a contributing factor to the decline. However, we have so far lacked knowledge on any spatiotemporal thresholds in landscape structure related to the decline. Here, we studied such thresholds in 16 5×5 km landscapes, systematically distributed within the study area. Local declines were most pronounced in the western (inland) part of the study area in 1980-85. At that time, the species already had gone extinct in the eastern (coastal) area. We related changes in landscape structure to the timing of the grey-sided vole declines. Landcover types (>0.25 ha) were digitized from aerial photographs within the 5×5 km landscapes with 5-yr intervals. The most pronounced changes in landscape structure were related to changes in forest age structure due to clear-cutting. Within the study area, there were significant geographical differences in the size distribution of clearcuts and forest patches. In 1970, the coastal in contrast to the inland study area, was characterized by more clear-cuts (766  versus 182) that were smaller (mean 5 ± 18 ha versus 13 ± 34 ha) but covered larger areas (sum 4077 ha versus 2325 ha). Spatio-temporal comparisons showed that the coastal landscape in 1970, when the vole was rarely found there, resembled the inland landscape in 1985. The main decrease in focal forest patch size in the inland occurred in 1980-85, coinciding with the major drop in vole numbers there. Our results suggest that spatio-temporal changes in landscape structure are important and contributing to declines in greysided vole abundance.