Nazwę szkół „tysiąclecia” (w języku potocznym nazywanych „tysiąclatkami”) powiązano z obchodzonymi oficjalnie uroczystościami 1000-lecia Państwa Polskiego, przypadającymi na 1966 rok. Hasło budowy „tysiąca szkół na Tysiąclecie Państwa Polskiego” rzucił Władysław Gomułka 24 września 1958 roku.
Pierwszą szkołą-pomnikiem została Szkoła Podstawowa nr 7 im. gen. Karola Świerczewskiego w Czeladzi, której uroczyste otwarcie miało miejsce 26 lipca 1959 roku. Wybór właśnie tej lokalizacji nastąpił za sprawą inicjatywy Jerzego Ziętka, a pracami kierował Jerzy Galon z sosnowieckiego Przedsiębiorstwa Budownictwa Mieszkaniowego. Budowę obiektu rozpoczęto 26 października 1958 roku; jest to 15-salowa placówka z kuchnią, stołówką i świetlicą. 26 lipca 1959 r. otwarto na Śląsku 32 szkoły. Przy budowie placówki pracowali m.in. żołnierze Wojskowego Korpusu Górniczego. Jeden z nich, ówczesny dowódca plutonu Tadeusz Góras, wspominał po latach:
Pierwszą szkołą-pomnikiem w Warszawie zostało XVII Liceum Ogólnokształcące z Oddziałami Dwujęzycznymi im. Andrzeja Frycza Modrzewskiego, pod które kamień węgielny został wmurowany 9 marca 1959 roku, oddane do użytku 28 czerwca 1960 roku.