Most parts of the Circumpolar Arctic have only discontinuous evidence for long-term human settlement. In contrast, Northern Norway has an unbroken archaeological record that extends back to the early Holocene. Numerous high-resolution archaeological and palaeoenvironmental records have been generated by commercial excavations and surveys, offering archaeologists unique opportunities to investigate long-term human ecodynamics in an Arctic coastal setting. To date, however, deeper analysis of the new datasets has yet to be undertaken. This paper aims to present a new synthesis of early and mid Holocene archaeological and paleoenvironmental sequences for Western Finnmark (11500-2000 cal BP). This enables us to identify three major phases of culture change that broadly correlate with climatic and environmental shifts. We then present emerging results from our multi-scalar analysis of the processes driving these transformations. At supra-regional and regional scales, our palaeodemographic modelling indicates major population events centered around 6000 cal BP and 4000 cal BP. At intra-regional scales, we are identifying spatial clustering of prehistoric settlements into local socio-economic communities. At the scale of local settlements, our analysis of house-pit chronologies is clarifying the degree of simultaneous occupation and re-use. We also draw on recent research into rock art and ritual landscapes in an effort to reconstruct the relationship between settlement clusters and general interaction patterns. Integration of these diverse lines of evidence is generating a vivid picture of thriving Arctic coastal communities, with indications that the timing and pace of cultural responses to climatic and environmental changes were more complex than previously thought.