Global climatic changes expected in the next centuries are likely to cause unparalleled vegetation disturbances, which in turn impact ecosystem services. To assess the significance of disturbances, it is necessary to characterize and understand typical natural vegetation variability on multi-decadal timescales and longer. We investigate this in the Holocene vegetation by examining a taxonomically harmonized and temporally standardized global fossil pollen dataset. Using principal component analysis, we characterize the variability in pollen assemblages, which are a proxy for vegetation composition, and derive timescale-dependent estimates of variability using the first-order Haar structure function. We find, on average, increasing fluctuations in vegetation composition from centennial to millennial timescales, as well as spatially coherent patterns of variability. We further relate these variations to pairwise comparisons between biome classes based on vegetation composition. As such, higher variability is identified for open-land vegetation compared to forests. This is consistent with the more active fire regimes of open-land biomes fostering variability. Needleleaf forests are more variable than broadleaf forests on shorter (centennial) timescales, but the inverse is true on longer (millennial) timescales. This inversion could also be explained by the fire characteristics of the biomes as fire disturbances would increase vegetation variability on shorter timescales, but stabilize vegetation composition on longer timecales by preventing the migration of less fire-adapted species.