Võru Kreutzwaldi Gümnaasiumi eelkäijaks on Võrumaa Rahvahariduse Seltsi venekeelne poeglaste gümnaasium, mis sai 1918. aastal õiguse jätkata eestikeelse koolina. Tööd alustati 10. septembril 1918. 1918-1920 oli koolijuhatajaks Aleksander Raudsepp. Õpilasi oli esimestel õppeaastatel 311-446, õppetöö oli tasuline. Paralleelselt tegutsevat tütarlaste gümnaasiumi juhatas pastor Artur Sommer.
1918. aastal puhkenud Vabadussõja tõttu jäi kooli tegevus napiks ning katkendlikuks. Suurenes vaesematest peredest pärit õpilaste arv, tunniplaanist lülitati välja usuõpetus, kooli raamatukogu täiendati mõisatest hangitud saksakeelse kirjandusega. 1918. aastal sai koolist mõneks ajaks nõukogulik õppeasutus, nn töökool, mis kandis nime Võru Töörahva Keskkool. Suurema osa 1919. aasta kevadsemestrist oli kool suletud, seejärel taastati endised gümnaasiumid. Direktoriks sai Johan Koemets.
1924. aastal oli tütarlaste gümnaasiumil kaks haru-humanitaarne ning kodumajanduslik. Klasse oli kokku 10, 273 õpilasele jagas õpetust 22 õpetajat. Poeglaste gümnaasiumis sai õppida humanitaar- või reaalharus. Klasse oli 11, õpilasi 325 ja õpetajaid 21. Kool töötas praeguse Võru Täiskasvanute Gümnaasiumi ruumides. 1924. aastal ehitati lastevanemate rahalise abiga kooli puitosale juurde kiviosa.
Kuna kaks kooli eksisteerisid koos-koolil oli üks ülalpidaja, ühised tööruumid, õpetajadki kattusid- ,siis pidas riik otstarbekaks gümnaasiumid ühendada. 1929 moodustati Võrumaa Rahvahariduse Seltsi ühisgümnaasium. Direktoriteks olid Edkar Oissaar, Johan Koemets, ja Feliks Pettai.
ENSV ajal suurenes õpilaste arv tunduvalt. Osa EV ja Saksa okupatsiooni ajal töötanud õpetajaid pidi lahkuma, nende asemel asusid ametisse NSV Liidus hariduse saanud õpetajad. Küüditamine tabas ka kooliperet. 1944. aastal korraldati ümber koolisüsteem. Kaotati õppemaks, hakati õpetama vene keelt ja kirjandust, NSVL ajalugu ja geograafiat. Kool hakkas kandma nime Võru I Keskkool. Kool tegutses endistes ruumides, direktorid olid Johan Koemets, Armanda Zarutskaja, Alice Tomberg ja Eduard Jupets.
1953. aastast kannab kooli Fr. R. Kreutzwaldi nime. 1958. aastal sai direktoriks legendaarne Ilmar Reiman. 1960. aastal koliti uude, suuremasse hoonesse, kus praegu töötab Võru Kesklinna Gümnaasium. Seal jätkus ruumi 880 õpilasele, rajati spordiväljak, internaat ja kaunis kooliaed. 1960. aastatel oli koolis võimalik omandada lukksepa, loomakasvataja, maaler-krohvija, põllumajanduse mehhanisaatori, õmbleja, müüja või pioneerjuhi eriala. Alguse sai matemaatika ja inglise keele süvaõpe.
1974. aastal kolis kool taas uude hoonesse, mis oli projekteeritud 1392 õpilasele. 1988. aastal tehti koolile juurdeehitus. Rajati spordiväljak ja kooliaed. Kool tõusis vabariigi tunnustatud koolide sekka. Kujunes välja süvaõppega klasside süsteem. Koolielus katsetati 40-minutilisi tunde, viidi sisse viiepäevane koolinädal, hakati korraldama sisseastumiskatseid.
EV ajal jätkusid koolielus suured muutused. Töötati välja kooli arengukava. Osaleti mitmetes üleriiklikes projektides nagu „Omanäoline kool“, „Uuriv õppimine“, tekkisid sidemed välismaaga. Gümnaasiumiosas hakati hindama 10-palli süsteemis. Kaasajastati süvaõppega klasside süsteemi ning õppimistingimusi. 2013. aastal sai koolipere alustada tööd kaasaegsete tingimuste järgi renoveeritud koolimajas. Töötasid hoolekogu, õpilasesindus ja tugispetsialistid. Regulaarselt ilmus „Infoleht“. Säilusid vanad traditsioonid ning tekkisid ka uued. Kooli juhtisid Ott Ojaveer ja Katrin Martinfeld.
Alates 1997. aastast kannab kool nime Võru Kreutzwaldi Gümnaasium.
VKG pakkus võimalust õppida 5 õppesuunal: infotehnoloogia, loodusteaduslik, matemaatika-inglise keele, sotsiaal- ja humanitaarõppesuund. Põhikoolis sai õppida süvendatult inglise keelt.
Kooli õpilased saavutasid kõrgeid kohti maakonna olümpiaadidel, konkurssidel, võistlustel. Aktiivsed õpilased osalesid rahvusvahelistes projektides.
Kooli kauaaegne tunnuslause „Ülemaks kui hõbevara, kallimaks kui kullakoormad tuleb tarkus tunnistada“ sai vastloodud põhikooli motoks.
Võru Kreutzwaldi Gümnaasium suleti 30. juunil 2015, kooli õpilased jätkasid õpingut Võru Kreutzwaldi Koolis.