The long-term ecological interactions between fire and the composition of dominant trees and shrubs in boreal and cold temperate Fennoscandian forests are still under discussion. We hypothesized that fire-prone taxa should abound during periods and regions characterized by higher fire disturbance, while fire-intolerant taxa should dominate when and where fire activity is low. Biomass burning (BB) is here investigated based on 69 sedimentary charcoal records. For the same sites, the relative contribution of pollen-based reconstructions of dominant vegetation cover divided into three different fire-sensitivity classes is explored by means of a statistical approach. The overall patterns found across Fennoscandia suggest that Ericaceae (mainly Calluna), Pinus, Betula and Populus are strongly positively correlated with multi-millennial variability of BB in both boreal and cold temperate forests, confirming their fire-prone character (taxa adapted/favoured by burning). Positive but much weaker (and not always significant) relationships also exist between long-term trends in BB and Fagus, Quercus, Corylus, Alnus, Juniperus, Carpinus and Salix, fire-tolerant taxa that survive low/moderate intense fires because of specific functional traits or their rapid, enhanced regeneration after fire. A strong negative significant correlation is instead detected between BB and Picea, Ulmus Tilia, Fraxinus, which are fire-intolerant taxa and can locally disappear for a short time after a fire. This large-scale analysis supports our initial hypothesis that tree and shrub dominance was closely linked to biomass burning since the onset of the Holocene in the study regions. Fire was an important ecosystem disturbance in Fennoscandia influencing long-term vegetation dynamics and composition over the last 11,000 years, although human activities probably altered the strength of fire-vegetation interactions during more recent millennia.