První zmínky o škole v Kostelci nad Labem se na stránkách kronik objevují již v 15. století, přesně roku 1465. Jak uvádějí prameny, šlo o školu partikulární o dvou třídách, do níž chodili odrostlejší žáci z města i okolí. Tato škola byla podřízena samotnému rektoru Karlovy univerzity.
Dalším významným datem historie vzdělávání je rok 1860 , kdy byla dosavadní škola „odstraněna„ a byl zakoupen dům č. 78, na jehož místě byla vystavěna nová jednopatrová školní budova, v níž je dnes umístěn první stupeň (1. až 5. postupný ročník). Tato škola byla na svou dobu velmi moderní, její plán byl dokonce roku 1868 vystaven na výstavě v Paříži.
Následně v roce 1895, při stále se zvětšujícím počtu obyvatel, byla v našem městě povolena zemskou školní radou nová měšťanská škola chlapecká. Nová budova na náměstí však nesloužila stále jen chlapecké měšťanské škole, roku 1899 lze v městské kronice číst zmínku o tom, že zde byla otevřena první třída dívčí měšťanské školy. Roku 1907 začíná přestavba měšťanské školy, o rok později je schválen návrh na školní zahradu.
Postupem času začíná úroveň školství v Kostelci nad Labem značně stoupat. Roku 1910 je zde zřízen čtvrtý ročník měšťanské školy, což nemá v celém okrese obdoby.
Okupace Československa hitlerovským Německem byla pro školu těžkou zkouškou. Vzešli z ní učitelé, kteří svým statečným a čestným postojem dali jasně najevo svůj nesouhlas s okupací a položili vlastní životy za svržení nenáviděného režimu a svobodu naší vlasti. Byli to odborní učitelé Jaroslav Lafek, Jaroslav Vančura, František Zeyval a Anna Stehlíková.
V letech 1945 – 1947 dochází k velkým opravám na obou budovách, jsou upravena okna, zaveden vodovod, záchody se splachováním, vybudováno kanalizační potrubí, nová elektrická přípojka, zaveden rozhlas, třídy se vybavují novým nábytkem a tabulemi.
Další změna proběhla v roce 1953, kdy byla spojena bývalá národní škola se školou střední a byla zřízena osmiletá střední škola. Škola měla celkem 17 tříd a působilo zde 19 učitelů.
Na jaře 1959 bylo započato s výstavbou dílen ve dvoře školy a už od 1. září 1959 bylo v dílnách zahájeno vyučování.
Školní budova č. 89 byla 16. února 1983 pro zcela nevyhovující technický stav uzavřena. Třídy byly umístěny v hlavní budově, kde za plného provozu školy probíhaly také stavební práce. Budova č. 89 byla po rekonstrukci znovuotevřena 14. března 1988 i s nově vybudovaným hřištěm na jejím pozemku.
U příležitosti 160. výročí úmrtí slavné kostelecké rodačky Terezy Stolzové, operní pěvkyně, byl rozhodnutím Ministerstva školství, mládeže a tělovýchovy ze dne 28. ledna 1994 Základní škole v Kostelci nad Labem propůjčen čestný název „Základní škola T. Stolzové“.
V roce 2013 proběhla rozsáhlá rekonstrukce budovy školy čp. 288 zaměřená na snížení energetické náročnosti. V rámci rekonstrukce byla vyměněna okna, zateplení pláště budovy a modernizace kotelny.
V roce 2015 byla vybudována nová moderní kotelna i na budově čp. 89.
2014 - 2016 rekonstrukce školního hřiště - vzniklo jedno víceúčelové hřiště a hřiště s atletickým oválem a umělým travním povrchem pro malou kopanou.
V roce 2018 se rekonstruovala WC na budově 288 a v budově 289.
V roce 2019 byla zrekonstruovaná zahrada za budovou čp. 89.
V budovách čp. 288 a 289 byla v roce 2019 zavedena rekuperační jednotka zajišťující stálou výměnu čerstvého vzduchu ve třídách.
V roce 2020 byla dokončena nová přístavba školy, která zahrnuje nové šatny, jídelnu, 7 kmenových učeben, 2 jazykové učebny, 1 přírodovědnou učebnu, odbornou učebnu pro výuku nové informatiky, dílny a knihovnu. Ve ŠD na budově čp. 289 byly vyměněny podlahy v učebnách a učebny byly vybaveny novým žákovským a úložným nábytkem.
V roce 2023 byla zrekonstruovaná bývalá jídelna a přilehlé prostory a wc v přízemí Adrie. Vznikla zda další učebna ŠD, šatny, sborovnička a zázemí pro vychovatelky ŠD, nové sociální zařízení pro žáky i pedagogy. Současně s rekonstrukcí také proběhla kompletní rekonstrukce střechy a výměna krytiny.
