The spatial distribution of kelp (Laminaria hyperborea) and sea urchins (Strongylocentrotus droebachiensis) in the NE Atlantic are highly related to physical factors and to temporal changes in temperature. On a large scale, we identified borders for kelp recovery and sea urchin persistence along the north-south gradient. Sea urchin persistence was also related to the coast-ocean gradient. The southern border corresponds to summer temperatures exceeding about 10°C, a threshold value known to be critical for sea urchin recruitment and development. The outer border along the coast-ocean gradient is related to temperature, wave exposure and salinity. On a finer scale, kelp recovery occurs mainly at ridges in outer, wave exposed, saline and warm areas whereas sea urchins still dominate in inner, shallow and cold areas, particularly in areas with optimal current speed for sea urchin foraging. In contrast to other studies in Europe, we here show a positive influence of climate change to presence of a long-lived climax canopy-forming kelp. The extent of the coast-ocean gradient varies within the study area, and is especially wide in the southern part where the presence of islands and skerries increases the area of the shallow coastal zone. This creates a large area with intermediate physical conditions for the two species and a mosaic of kelp and sea urchin dominated patches. The statistical models (GAM and BRT) show high performance and indicate recovery of kelp in 45-60% of the study area. The study shows the value of combining a traditional (GAM) and a more complex (BRT) modeling approach to gain insight into complex spatial patterns of species or habitats. The results, methods and approaches are of general ecological relevance regardless of ecosystems and species, although they are particularly relevant for understanding and exploring the corresponding changes between algae and grazers in different coastal areas.