Herbivores influence the structure of plant communities in arctic-alpine ecosystems. However, little is known of the effect of herbivores on plant colonisation following disturbance, and on its variability depending on the identity of herbivores and the characteristics of the habitats. To quantify the role of large and small vertebrate herbivores, we established exclosures of two different mesh sizes around disturbed subplots in forest and nearby tundra habitats in four contrasting locations in the forest-tundra ecotone in northernmost Sweden and Norway. The study revealed that herbivores influenced the abundance but not the species composition of regenerating vegetation. Gaps were colonised by the dominant species in the surrounding vegetation. The only exception to this expectation was Empetrum nigrum, which failed to colonise gaps even though it dominated undisturbed vegetation. Significant effects of herbivory were only detected when both small and large herbivores were excluded. Herbivores decreased the abundance of three of the most common species Vaccinium myrtillus, Vaccinium vitis idaea, and Deschampsia flexuosa. The effect of herbivory on the abundance of these three species did not differ between habitats and locations. However, the composition of the regenerating vegetation differed between habitats and locations. The disturbance treatment increased the species richness on the scale of plots, habitats, and sites. However, on the scale of whole locations, all species found in disturbed areas were also found in undisturbed areas, suggesting that the natural disturbance regime in arctic landscapes is high enough to sustain colonising species.