Permafrost in steep slopes has been increasingly studied since the early 2000s in conjunction with a growing number of rock-slope failures, which likely resulted from permafrost degradation. In Norway, rock-slope destabilization is a widespread phenomenon and a major source of risk for the population and infrastructure. However, the lack of precise understanding of the permafrost distribution in steep slopes hinders the assessment of its role in these destabilizations. This study proposes the first nation-wide permafrost probability map for the steep slopes of Norway (CryoWall map). It is based on a multiple linear regression model fitted with multi-annual rock surface temperature (RST) measurements, collected at 25 rock-wall sites, spread across a latitudinal transect (59–69° N) over mainland Norway. The CryoWall map suggests that discontinuous permafrost widely occurs above 1300–1400 and 1600–1700 m a.s.l. in the north and south slopes of southern Norway (59° N), respectively. This lower altitudinal limit decreases in northern Norway (70° N) by about 500 ± 50 m, with more pronounced decrease for south faces, in reason of the insolation patterns largely driven by midnight sun in summer and polar night in winter. Similarly, the mean annual RST differences between north and south faces of similar elevation range around 1.5 °C in northern Norway and 3.5 °C in southern Norway. The CryoWall map is evaluated against direct ice observations in steep slopes and discussed in the context of former permafrost studies in various types of terrains in Norway. We show that permafrost can occur at much lower elevations in steep rock slopes than in other terrains, especially in north faces. We demonstrate that the CryoWall map is a valuable basis for further investigations related to permafrost in steep slopes in both practical concerns and fundamental science.