The oldest early Mesolithic settlements found so far (i.e. 8600 B.P.) in the interior of northern Sweden, in the province of Norrbotten, have been discovered through the application of a model simulating glacio-isostatic land uplift. The objective of this study was to investigate, through pollen and charred particle analyses, vegetation composition and the influence of man on vegetation and fire pattern in the vicinity of two of these early settlements. Early Holocene vegetation was characterised by Betula, Hippophaë and Salix-species, but no initial impact by hunter-gatherers on vegetation was detected. Subsequently Betula and Pinus became dominant but abrupt changes in the tree layer followed, Poaceae, Hippophaë and Salix-species increased, and Humulus occurred. These changes, which were synchronous with dates of archaeological findings at the settlements, indicated local vegetation changes caused by man. The relationship between these changes and fire was, however, subtle. Eventually Pinus forests became dominant and human impact on vegetation became less apparent. It is concluded that the impact of early Mesolithic hunter-gatherers on vegetation was detectable, but that their effect on fire pattern was difficult to evaluate. Further, we show that the glacio-isostatic land uplift must be considered in the search for Mesolithic settlements in areas previously covered by the Weichselian Ice, and that the process has influenced the biological archives through re-deposition of material. © Springer-Verlag 2005.