Szkoła Podstawowa nr 4 w Legionowie powstała w 1936 roku. Jej siedzibą były dwa prywatne budynki przy ulicy Bandurskiego. Pierwszym kierownikiem został pan Bolesław Sobolewski. Z powodu działań i zniszczeń wojennych w pracy szkoły nastąpiła 11- letnia przerwa. Działaność swoją placówka wznowiła w roku szkolnym 1955/1956. Naukę w szkole rozpoczęło wówczas 238 uczniów, a pracowało z nimi pięcioro nauczycieli. Pierwszą powojenną kierowniczką szkoły została pani Anna Budzanowska. Praca i nauka odbywała się w trudnych warunkach lokalowych, w odbudowanym ze zniszczeń wojennych prywatnym budynku przy ulicy Kościelnej ( obecnie ul. Jana Pawła I).
W kolejnych latach szkołą kierowali: pani Genowefa Zawodniak, pan Józef Cichocki, pan Ryszard Tyrcha, pani Halina Głuszcz, pani Teresa Dobosz, pani Teresa Bednarska, pani Halina Woźnicka. Na początku 1985 roku powstał Społeczny Komitet Rozbudowy Szkoły Podstawowej nr 4 w Legionowie skupiający jej byłych uczniów i nauczycieli. Przewodniczącym został pan Emil Paterek. Kuratorium Oświaty i Wychowania wykupiło od prywatnego właściciela budynek i działkę o powierzchni 1,47 ha, a Społeczny Komitet zorganizował zbiórkę pieniędzy od rodziców i organizacji społecznych.
Pracownia pana Leszka Zaremby opracowała piękny projekt z pracowniami, stołówką, amfiteatrem i salą gimnastyczną, doskonale wkomponowany w zadrzewiony teren. Władze miasta przekazały nadwyżkę budżetową. Rozbudowę rozpoczęto w 1990 roku, realizując ją w trzech etapach. W tych latach dyrektorem szkoły była pani Grażyna Rzewuska. W roku 1991, po długich, bo aż sześcioletnich zmaganiach i zaangażowaniu ówczesnego Prezydenta Mista Legionowo pana Andrzeja Kicmana, wiceprezydenta Wojciecha Jeute, dyrektor szkoły pani Grażyny Rzewuskiej i obecnego Prezydenta Miasta Legionowo pana Romana Smogorzewskiego, rozbudowana szkoła została oddana do użytku. Zachwyciła wówczas dużą ilością jasnych, przestronnych sal lekcyjnych, nowoczesną stołówką, pięknym patio. Na salę gimnastyczną przyszło uczniom jeszcze poczekać kolejnych kilka lat, gdyż zrealizawano to dopiero w trzecim etapie rozbudowy, czyli w roku 1996. Również od tego roku uczniowie SP 4 mogli cieszyć sie nowoczesną biblioteką wraz z powiekszającym się z roku na rok księgozbiorem oraz przestronną czytelnią.
W roku 2000 szkoła stanęła przed kolejnym ambitnym zadaniem- wyborem patrona. Spośród wielu propozycji środowisko szkolne wybrało imię Legionów Polskich 1914-1918. Wybrano bohatera zbiorowego, upamiętniając tym samym ludzi, którzy wywalczyli wolność ojczyźnie po 123 latach niewoli. Imię patrona zostało zatwierdzone Uchwałą Rady Miejskiej w Legionowie z dnia 16 sierpnia 2000 r.
Po nadaniu szkole imienia przyszła kolej na sztandar. Posiada on barwy biało- czerwone. Na pierwszej stronie, na czerwonym tle- widnieje otwarta księga, a na niej ułożona została czapka legionisty, wokół napis- Szkoła Podstawowa nr 4 im. Legionów Polskich 1914-1918, poniżej: Legionowo 2000. Druga strona w bieli - na czerwonym polu w kształcie koła srebrny orzeł w koronie. Wokół ważne słowa- ,, Bóg, nauka, honor, ojczyzna". Projekt sztandaru wykonała nauczycielka naszej szkoły pani Dorota Hepner. W dniu 10 listopada 2000 roku nastąpiło uroczyste nadanie szkole imienia, poświęcenie sztandaru, ucniowie zaś po raz pierwszy w historii szkoły ślubowali na sztandar. Dnia 1 września 2004 roku Szkoła Podstawowa nr 4 połączyła się z Przedszkolem Miejskim nr 14 i w ten sposób weszła w skład Zespołu Szkolno- Przedszkolnego. Dokonano wówczas modernizacji budynku pod kątem przystosowania go dla przedszkolaków.
W związku z systematycznie zwiekszającą się liczbą uczniów zaczęto myśleć o rozbudowie szkoły. Dokonano tego w roku 2010. Najpierw jednak wszyscy uczniowie wraz z nauczycielami musieli opuścić mury szkolne i przenieść się na jeden cały czerwcowy miesiąc w gościnne progi Szkoły Podstawowej w Łajskach. Było to dużym wyzwaniem logistycznym i skomplikowanym przedsięwzięciem, któremu jednak zarówno gospodarze, jak i goście podołali z pieśnią na ustach. Także we wrześniu w szkole trwały intensywne prace remontowe, ale uczniowie wrócili już do swojego gmachu. Nastąpiło otwarcie nowego piętra szkoły, na którym mogły podjąć naukę klasy 1-3. Sale były przestronne, jasne z półokrągłymi oknami dodatkowo doświetlającymi wnętrza. Na drugim piętrze szkoły znalazło się miejsce dla sali artystycznej, komputerowej, sali ćwiczeń i rekreacji oraz świetlicy szkolnej. Od czasu rozbudowy, uczniowie SP4 mogli się również cieszyć nowym boiskiem sportowym, bieżnią, placem do gier terenowych, boiskiem do rekreacyjnej gry w koszykówkę. Powstał też nowy plac zabaw dla przedszkolaków.
Rok 2011 był także rokiem rozpoczęcia działalności Gimnazjum nr 6 w Zespole Szkolno- Przedszkolnym. Kolejna reforma spowodowała, że od roku szkolnego 2017/2018 zaczęło się wygaszanie gimnazjów. Ostatni rocznik gimnazjalistów został pożegnany w roku szkolnym 2018/2019.
W roku 2014/2015 kierowanie szkołą obejmuje pani Agnieszka Kobylińska. Podczas swojej kadencji pani dyrektor dba o to, aby szkoła była bezpieczna, radosna i aby sprzyjała efektywnej nauce oraz mądremu wychowaniu.