Schools have been identified as ideal settings for health promotion (HP) among children, adolescents and school staff. Most European countries have established strategies to implement HP into their school system, however, little is known about these national strategies and how effective they have been. School HP implementation concerns processes of adoption, adaptation and operation of a complex intervention into a complex setting. This study analyses the processes that have led to school HP implementation in Scotland from the 1980s until now to identify key factors which facilitated and supported effective implementation. In the tradition of case-study research, 14 interviews with representatives of national and local organizations involved in school health, as well as with school staff were conducted. Furthermore, policy documents, reports and guidelines were collected. The data were analysed following a Grounded Theory approach. Four phases of school HP implementation into the Scottish school system were identified: (i) getting started (1980s–1998), (ii) political will and strategic vision (1999–2001), (iii) national leadership (2002–2008), and (iv) integration and embedding into education system (2008–ongoing). Throughout the phases political will and committed actors, the strategy/tradition to give power to the local authorities and individual schools, and the establishment of partnerships and ownership have supported implementation. Scotland is an interesting case giving important insights into the ways and possibilities of negotiating an interdisciplinary and cross-sectoral theme such as HP in schools. Further research concerning different political systems and national implementation processes is important to widen the understanding of national implementation strategies of school HP.