Narva Kreenholmi Gümnaasium alustas oma ajalugu 1. septembril 1945. aastal 4. algkoolina. Linna tervishoiuosakond eraldas kolm palatit linnahaigla (Kreenholm 52) pooleldi lagunenud hoone lõunatiivas, kohandades need õppetööks. Ivangorodis Parussinkal eraldas Kreenholmi manufaktuuri juhtkond Narva jõe paremal kaldal elanud noorematele kooliõpilastele (1. ja 2. klassi õpilastele) ruumi õppimiseks kahes vahetuses. 1945. aasta detsembris oli Kreenholmi koolis juba 234 õpilast: kolm esimest ja kolm teist klassi. Esimesed õpetajad: Serafima Antipova, Tatjana Granatkina, Jekaterina Grigorjeva, Zinaida Klimberg, Natalja Nepljujeva, Jefrossinja Moroz, Ivan Jasnov.

1946. aastal oli kool linnas suurim (515 õpilast). Koolile eraldati lisaruumid haiglahoones.
1947. aasta septembris avati Kõrgesoo alevikus üks klassikomplekt, mis kuulus 4. algkooli koosseisu. 1948. aastal läksid Parussinkal asuvad klassid üle Leningradi oblasti Kingissepa Rahvahariduse osakonna alluvusse.
1948. aastal toimus esimene neljandate klasside lend, kes sooritasid eksameid neljas õppeaines: vene keeles kirjalikult ja suuliselt, aritmeetikas kirjalikult ja eesti keeles suuliselt.
Kuna koolis oli kitsas, õppetegevus toimus kolmes vahetuses. 1949. aasta septembriks viidi kool haiglahoonest üle teise ruumi, mille vabastas miilitsaosakond (praegu Joala 24). Koolile eraldati selle hoone lõunaosa.
1951. aasta septembris sai kool uue, spetsiaalselt kooli jaoks ehitatud hoone Pargi tänaval (alates 1953. aasta jaanuarist kannab tänav Vassili Gerassimovi nime). Koolis oli 12 klassi. Kõrgesoo alevikus õppis 26 1.-4. klassi õpilast.

ENSV Haridusministeeriumi 12. juuni 1952. aasta käskkirjaga reorganiseeriti 4. algkool 7-aastaseks. Sama käskkirjaga Kõrgesoo klassid moodustasid iseseisva Kõrgesoo algkooli. Seoses ümberkorraldustega vajas kool rohkem aineõpetajaid. Tulid uued õpetajad. Õpilaste arv kasvas. 1954. aastal toimus esimene seitsmenda klassi lend.

ENSV haridusministri käskkiri 23. augustist 1955. aastast reorganiseeris 4. seitsmeaastase kooli keskkooliks (10 klassi). See tõi kooliellu suuri muudatusi. Algklassides võeti kasutusele käsitöötunnid, vanemates põllumajandus-, masina- ja elektriõpetuse praktikumid. Kooli juurde tekkis viljapuuaed.
1958. aasta oli kooli jaoks märkimisväärne ja tähtis. Toimus kümnenda klassi esimene lend. Aastatel 1958-1971 töötasid kooli juures abiklassid.

Seoses uute koolide (6. ja 7. kooli) avamisega linnas otsustas Narva Linnavalitsus keskkooli nr 4 reorganiseerida 1960. aasta 1. septembrist 8-aastaseks. Samal, 1960. aastal avati kooli juures muusikaklassid, mis töötasid 1994. aastani.

1963. aastal, vaatamata sellele, et kool oli arvestatud 880 õpilasele, õppis koolis 1200 last. Seetõttu otsustas Narva Linnavalitsus rajada koolimajale juurdeehitis. Tööd lõpetati 1966. aastal, mille tulemusena sai kool 10 uut klassiruumi.

1968. aastal reorganiseeriti 8-aastane 4. kool uuesti keskkooliks. 1970. aastal alustati spordikompleksi ehitamist basseini ja suure aktusesaaliga. Töö lõpetati 1973. aastal. 1971. aastal võeti koolis kasutusele algse sõjaväelise ettevalmistuse õpetamine.

1975/76. õppeaastal töötas kooli pedagoogiline kollektiiv kabinetisüsteemi loomise nimel. 37 kabinetist 24 saavutas suurepärase ja hea taseme. Koolis töötas 57 õpetajat ja õppis 1328 õpilast.

1977. aastal otsustas NSV Liidu Haridusministeerium luua õppevahendite ja koolimööbli tugikoolid. Eestis oli ainsaks selliseks kooliks Narva 4. keskkool. Kool varustati tehniliste seadmetega (filmiprojektorid, diaprojektorid, magnetofonid, kodoskoobid, plaadimängijad), mida õpetaja sai kasutada tunni läbiviimisel. Kreenholmi manufaktuuri töötajad paigaldasid keemiakabinetis iga õpilase töökoha juurde elektri ja vee. Peale selle kooli nr 12 avamine võimaldas 1977. aasta septembrist minna üle õppele ühes vahetuses. Iga algkooli klass sai endale kabineti.

1978. aasta märtsis Gertruda Fjodorovna Sedova korraldas „Helesinise patrulli“ maleva, mis osales 1984. aastal Rahvamajanduse Saavutuste Näitusel ja sai sellel näitusel auhinnaks pronksmedali.
1986. aastal avati koolis esmakordselt klass koolieelikutele, kus õpetasid Zoja Nikolajevna Salidor ja Julia Vassiljevna Lossjeva.

Aastal 1986 avati koolis esimene arvutiklass linnas, mis oli varustatud arvutitega „Agat“. Arvutiõpetuse aluseid õpetas Galina Petrovna Dmitrijeva.

1. septembril 1988. aastal läks kool üle 11-aastasele õppele nagu kõik Eesti koolid.
1994. aastal ei olnud koolilõpetajaid, kuna kool läks üle 12-aastasele õppele. Aastast 1994 kool kannab nime Kreenholmi Kool.
2003. aastal sai ta Narva Kreenholmi Gümnaasiumi staatuse. 1996. aastal sai koolis alguse uus traditsioon – rebaste ristimine.

1998. aastal ehitati koolihoone juurde veel üks juurdeehitis – garderoob ja raamatukogu. 2000. aastast kuni 2003. aastani teostati kooli vana hoone kapitaalne remont.

Aastast 1999 ilmub koolis meie iga-aastane ajakiri OUR GENERATION („Meie Põlvkond“), mille toimetajaks on praegu Natalja Timonina.

2023. aastal sai Narva Kreenholmi Kooli staatuse.

Kooli direktorid:

Aleksei Randin	31.08.1945.a. – 16.09.1946.a.
Zoja Timošjuk	16.09.1946.a. – 22.11.1948.a.
	27.02.1950.a. – 17.08.1953.a.
Polina Mihhailova	22.11.1948.a. – 10.06.1949.a.
Aleksandra Batišjeva	10.06.1949.a. – 27.02.1950.a.
Svetlana Boborenko	17.08.1953.a. – 21.10.1962.a.
Maria Nezamajeva	01.12.1962.a. – 12.02.1969.a.
Maria Lukjanenkova	01.09.1969.a. – 05.05.1982.a.
Aleksandr Nikolajev	05.03.1982.a. – 05.05.1988.a.
Albina Sitina	01.09.1988.a. – 01.09.1991.a.
Galin Moldon	01.09.1991.a. – 01.01.1994.a.
Jelena Torokvei	01.01.1994.a. – 14.12.2005.a.
Gennadi Bõkov	14.12.2005.a. – 30.10.2013.a.
Henri Kallaste	18.03.2014.a. – 27.05.2014.a.
Irina Janovitš	28.05.2014.a. – 25.10.2022.a.
Irina Bahramova	20.01.2023.a.