Land-use change can strongly affect wildlife populations, typically via habitat loss and degradation where land use expands, and also via increasing potentially available habitat where land use ceases. Large mammals are particularly sensitive to land-use change, because they require large tracts of habitat and often depend on habitat outside protected areas unless protected areas are very large. Our research question was thus how land-use change around protected areas affects large mammals’ habitat. Russia experienced drastic land-use change after the breakdown of the Soviet Union and – fortunately – wildlife data has been collected continuously throughout this time inside protected areas. We used long-term winter track count data for wild boar (Sus scrofa), moose (Alces alces), and wolf (Canis lupus) to assess habitat change inside and outside of Oksky State Nature Reserve from 1987 to 2007 using a time-calibrated species distribution model. Our results showed a constantly high share (at least 89%) of suitable habitat within the protected area’s core zone for each species, yet also substantial habitat increases of up to 23% within the protected buffer zone, and similarly, up to 27% outside the protected area. Of the variables we evaluated, post-Soviet land-use change, particularly farmland abandonment, was the main driver of this expansion of potential habitat for the three species we assessed. Our study highlights that strictly protected areas have been playing an important role in preserving wildlife in European Russia since 1991, and also that their surroundings provide much suitable habitat for large mammals. Post-Soviet land-use change in the surroundings of protected areas may provide opportunities to increase and connect wildlife populations.