Današnja Gimnazija Matije Antuna Reljkovića u Vinkovcima jedna je od najstarijih škola u sjeveroistočnoj Hrvatskoj, tj. u Slavoniji. Osnovana je 1766. godine u Petrovaradinu odlukom carice i kraljice Marije Terezije (1740.-1780.) kao latinska škola, te je predana isusovcima na upravljanje. Nakon austrijskog ukidanja isusovačkog reda 1773. godine, škola prelazi u državnu, odnosno vojnu upravu.

Novom odlukom Marije Terezije 1779. godine škola je prebačena iz Petrovaradina u Vinkovce, zajedno sa Školskim povjerenstvom za slavonsko-srijemsku granicu, vjerojatno zbog povoljnijeg položaja Vinkovaca u Vojnoj granici i mogućeg učinkovitijeg prosvjetno-kulturnog djelovanja. S potpunim radom u Vinkovcima škola je započela 1. studenog 1780. godine u savezu sa glavnom školom (pučkom školom), i to s dva viša latinska razreda. Na početku nije bilo puno učenika pa je nastavu mogao obavljati besplatno ravnatelj Školskog povjerenstva Franjo Engelbrecht koji je ujedno obavljao funkciju školskog prefekta.

Prelaskom Školskog povjerenstva i gimnazije u Vinkovce, grad postaje osim vojnog i obrtnog centra i prosvjetno-kulturni centar Granice, a zadatak nove obrazovne institucije po austrijskim vojnim vlastima je bio, pripremanje odanog časničkog, svećeničkog, liječničkog i činovničkog kadra  za potrebe državnih službi.

Godine 1792. je c. kr. Dvorsko vijeće donijelo odluku da se škola proširi s dva latinska razreda na četverogodišnju gimnaziju kako je bilo uređeno i u  drugim dijelovima Carevine. Učitelj u trećem i četvrtom gramatikalnom razredu bio je Matija Krmpotić. Ubrzo (1796) je na traženje Školskog povjerenstva gimnazija proširena na još dva humanistička razreda 5. i 6., a nastavu preuzima vinkovački rimokatolički župnik Josip Stjepan Relković Ehrendorfski, najstariji sin Matije Antuna Relkovića. U početku je nastavni jezik latinski.

Školom upravlja još uvijek prefekt tj. prvi državni učitelj u školi. Na prijelazu stoljeća školu pohađa oko 30 učenika, a nastavni kadar je 3-4 profesora. Vinkovačka je Gimnazija tada bila šesta gimnazija u današnjoj Hrvatskoj, nakon zagrebačke, riječke, požeške, senjske i osječke, a prva u Slavonskoj Vojnoj granici od Zagreba do Zemuna.

Za ovaj najstariji period ostalo je malo originalnih povijesnih izvora jer se do arhive tada malo držalo, ali zato imamo znanstveno povijesnu spomenicu povjesničara  profesora Mije Brašnića pod  naslovom  “Ces. Kralj. Velika gimnazija u Vinkovcih za prvog stogodišnjeg svog obstanka 1780. – 1879.” koju je napisao za potrebe prve stogodišnje proslave, a  rasvijetlila nam je  najstariju povijest škole.

Povećanjem broja, učenika, nastavnika, te razrednih odjeljenja tijekom 19. stoljeća, Gimnazija je postala najznačajnija prosvjetno-kulturna ustanova u gradu.

Krajem 1801.g. umro je Josip Stjepan Relković, vinkovački župnik i profesor humanističkih 5. i 6. razreda, te školski vjeroučitelj, ostajući brojnim gimnazijalcima u dugom sjećanju.

Godine 1822. c. kr. Dvorsko vojno vijeće odredi da brigadir Brodske pukovnije bude i ravnateljem Gimnazije, funkcija gimnazijskog prefekta je ostala netaknuta, on je upravljao i drugim normalnim školama u gradu u ime Školskog povjerenstva. Tridesetih godina 19. stoljeća gimnazija je brojala 70-tak učenika i 7 profesora, a od toga su bila 1 vjeroučitelj, 4 gramatikalna učitelja i 2 humanistička učitelja. Zapovjedništvo Brodske pukovnije godišnje je izdvajalo u prosjeku 4130 forinti na izdržavanje nastave u Gimnaziji. Stipendiju je primalo 11 učenika. Nastavnim planom u školi su se predavali: vjeronauk, latinski, povijest, zemljopis, prirodopis i matematika, te nešto kasnije i grčki jezik.

Godine 1850. u vinkovačku Gimnaziju uveden je hrvatski jezik kao zaseban predmet pod nazivom “ilirski jezik”, a iduće godine škola dobiva status “Cesarsko-kraljevska katolička državna velika gimnazija”. U 1852. godini u školu je uveden njemački jezik kao nastavni umjesto do tadašnjeg latinskog djelovanjem Bachovog apsolutizma. Hrvatski jezika za nastavne predmete vjeronauk i povijest uveden je najprije zalaganjem  đakovačkog biskupa Josipa Jurja Strossmayera i novog bana, podrijetlom Vinkovčanina baruna Josipa Šokčevića. Bilo je to 31. listopada 1860. godine.

Od 2. ožujka 1861. godine u školi je utemeljeno “Društvo za podupiranje vrijednih i siromašnih učenika”. Pokrovitelj i utemeljitelj Društva bio je đakovački biskup sa 1.000 forinti, a članovi utemeljitelji bili su još ban Josip Šokčević, obitelj grofova Khuen s vlastelinstva u Nuštru, zatim brojni graničarski časnici, te župnici, kanonici, vinkovački trgovci i odvjetnici.

Jedan od značajnijih događaja se dogodio 16. veljače 1868. godine. Car Franjo Josip I. donio je odluku da se u graničarskim školama, pa tako i u vinkovačkoj Gimnaziji, izjednače hrvatski i njemački jezik. Od iduće godine na prijedlog nastavničkog vijeća vojne vlasti dozvoljavaju postepeno uvođenje hrvatskog jezika kao nastavnog od prvih razreda.

Krajem školske godine 1875./1876. održana je prva matura na hrvatskom jeziku. Među tadašnjom generacijom učenika koji su maturu polagali na hrvatskom jeziku bio je i budući hrvatski književnik Josip Kozarac.

Iz godine u godinu broj učenika se povećavao pa je stara zgrada  (dvije visoke prizemnice) u kojima se održavala nastava postala pretijesna. Graničarske vlasti donose odluku da se na istom mjestu u centru grada sagradi nova zgrada. Gradnja je započela u lipnju 1878. , a završila u kolovozu 1879. godine a o tome svjedoče povijesni izvori. Tako je stogodišnjica vinkovačke Gimnazije svečano proslavljena 4. listopada 1879. useljenjem u novu, današnju školsku zgradu. Posvetu Gimnazije i svih učionica obavio je tadašnji đakovački biskup J.J. Strossmayer koji je bio i jedan od mecena u izgradnji nove zgrade.

U drugoj polovici 19. stoljeća gimnaziju je pohađalo godišnje iznad 200 učenika pretežno katoličke vjeroispovijesti, a nastavu je držalo dvadesetak profesora. U doba bana Ivana Mažuranića u školu se upisuju i mladež pravoslavne i židovske vjeroispovijesti, jer se ukidaju crkvene-narodne škole.

Nakon što je carskom odlukom 15. lipnja 1881. ukinuta Vojna granica, a njen teritorij  uključen u građansku Hrvatsku i Gimnazija potpada pod upravu Kraljevske zemaljske vlade u Zagrebu. Tom prigodom je dobila novi naziv: “Kraljevska velika gimnazija u Vinkovcima”. Dolaskom Khuena Hedervarya na mjesto bana u Hrvatskoj 1883. godine, započinje madžarizacija Hrvatske. Ona se posebno osjećala u vinkovačkom kraju zato što je u Nuštru Khuen imao svoj veleposjed. Khuen u Vinkovcima gradi veliku madžarsku školu. Učenici gimnazije u to vrijeme često izlaze na ulice u demonstracije protiv otvaranja madžarskih tzv. “julijanskih” škola i drugih oblika madžarizacije.

Gimnazija je na kraju 19. stoljeća najvažnija kulturno-prosvjetna ustanova u gradu i širem geografskom području od Pečuha do Hercegovine, od Novske do Zemuna, to vidimo po upisu učenika s tih područja.

Godine 1900/1901. školu pohađa 343 učenika, a na školi je uposleno 20 profesora. Školske vlasti dopuštaju djevojkama privatno polaganje mature. Prva učenica upisuje redovno pohađanje gimnazije 1907. godina. Bila je to Mira Hercigonja, čiji je tata, Mijo Hercigonja, bio profesor na školi. Učenica je za vrijeme odmora odlazila s profesorima u zbornicu.

U Prvom svjetskom ratu Gimnazija proživljava teške dane. Od ljeta 1914.godine do siječnja 1916. školska zgrada služi kao velika vojna bolnica za Istočno i Balkansko bojište. Kada je napravljena  nova, montažna vojna bolnica uz željezničku prugu Vinkovci-Vukovar, na polju pokraj sela Bršadin, tzv. “drveni Beč”, preseljenjem ranjenika i bolesnika, učenici i profesori se vraćaju u svoju zgradu. Za vrijeme Prve Jugoslavije, škola mijenja naziv u “Državna klasična gimnazija u Vinkovcima”. Beogradsko je Ministarstvo prosvjete željelo postepeno dokinuti gimnaziju krajem 1927.g. Cijelu stvar spašava gradska deputacija koja je upućena u Beograd, te je odluka ministarstva poništena. Nakon uvođenja šestosiječanjske diktature 1929. godine i nove teritorijalne podjele Jugoslavije na 9 banovina, Vinkovci su ušli u tzv. Drinsku banovinu. Tada se u školu uvodi  srpski jezik i ekavica kao nastavni i to traje sve do 1931. godina, kad je kotar Vinkovci, ipak dodijeljen Savskoj banovini. Novi nastavni jezik je bio srpsko-hrvatsko-slovenski. Od 1920. do 1941.  direktor škole je Hrvat, dr. Dragutin Poljugan, politički projugoslavenski orijentiran. U školi se to dobro osjetilo. Tijekom 1934. godine škola ponovno mijenja naziv, ali sada i program. Ukidaju se klasični predmeti, a novi naziv je “Državna realna gimnazija”.

U vrijeme Drugog svjetskog rata 1941.-1945. godine školsku zgradu najprije zauzima madžarska vojska, potom njemačka koja je koristi kao ratnu bolnicu. Nastava je svedena na minimum, pojedina polugodišta ratnih godina traju dva-tri mjeseca, a 1944. godine po 15-tak dana. Jedan dio učenika i nastavnika pristupio je antifašističkoj borbi. U ratu je školska zgrada oštećena iznutra i izvana, uništen je školski namještaj, učila, te dio školske knjižnice i arhive. Po tadašnjem Godišnjem izvješću 1942./43. godine školu pohađa 802 učenika(ce), a zaposlenih nastavnika bilo je 35 i 5 pomoćnih.

Pet godina poslije rata trajala je obnova zgrade, namještaja, učila, knjižnice i drugih školskih sadržaja. Školske godine 1956./57. godine vlasti FNR Jugoslavije i NR Hrvatske provode novu reformu školstva. Uvodi se obvezno osmogodišnje školovanje tako da niži razredi gimnazije prelaze u osmogodišnje škole, a četiri viša razreda ostaju u sklopu gimnazije kao I. II. III. i IV. razredi. Tada se reformom gimnazija uvode dva smjera: društveno-jezični, i prirodoslovno-matematički. Nova reforma 1963. godine ponovno klasificira gimnazije u Hrvatskoj, a vinkovačka postaje Opća gimnazija. Tri godine kasnije, Skupština Općine Vinkovci mijenja naziv škole u Gimnazija “Matija Antun Reljković”.

Školske godine 1975/76. započinje “Šuvarova” reforma koja teži dokidanju gimnazija (i elitnih slojeva u socijalističkom društvu) te afirmaciji proizvodno-uslužnih zanimanja. Nove srednje škole podijeljene su unutar sebe na pripremnu i usmjerenu fazu školovanja za pojedina zanimanja u trajanju od po dvije godine. Raznorazne srednje škole udružuju se u velike obrazovne centre. Gimnazija se udružuje sa Srednjom medicinskom školom “Dr. Zlatan Sremec” u Centar za usmjereno obrazovanje “M. A. Reljković”. Rješenjem Republičkog SIZ-a za prosvjetu, kulturu i fizičku kulturu od 10. listopada 1977. godine,  završni stupanj obrazovanja dobivali su učenici: za odgajatelje, suradnike u nastavnom procesu, knjižničare, inokorespondente, informatičke pomoćnike, medicinske sestre i zdravstvene tehničare. Za vrijeme uhodavanja reforme srednjeg obrazovanja polako su se gasile gimnazije, 1978. završeni su posljednji programi, a formalno-pravno prestale su postojati 1. siječnja 1981. godine.

Mnogi programi nekadašnjih gimnazija zadržani su u manjoj ili većoj mjeri kroz pripremnu i tzv. usmjerenu fazu srednjoškolskog obrazovanja. Godine 1984. broj upisanih učenika(ca) je 1138, a nastavnika je zaposleno 58, te 14 vanjskih suradnika. Sljedećih godina broj učenika se povećao na 1200. Nakon velikih društvenih promjena 1990-ih dolazi do polaganog vraćanja gimnazija i ukidanja “Šuvarovog” sustava školstva. Novoformirane vlasti, nakon višestranačkih izbora  u Republici Hrvatskoj,  odlučuju se na obnavljanje gimnazija i drugih starih srednjih škola, umjesto dotadašnjih velikih obrazovnih centara. Tako je Odlukom Skupštine općine Vinkovci 5. lipnja 1991. godine obnovljena Gimnazija “Matije Antuna Reljkovića” u Vinkovcima.

U svojih 230. godini postojanja u Vinkovcima, Gymnasium, kako piše na pročelju zgrade, teško je stradao u Domovinskom ratu 1991./95., jer je bio pogođen brojnim artiljerijskim projektilima od Srbočetnika iz Mirkovaca i Ostrova, zapravo svojih bivših učenika. Od tada do danas škola se stalno obnavlja i oprema uz pomoć Vlade Republike Hrvatske i donatora iz zemlje i svijeta koji su i sami pohađali ovu školu. Izuzetnim zalaganjem ravnatelja profesora Stipe Tomića i državnim ulaganjima preuređeno je staro krovište gimnazijske zgrade u nove školske učionice i kabinete. Nekadašnji tavanski prostori u kojima su živjeli gradski golubovi sada su postali najreprezentativniji prostori naše škole. Narednih se godina priprema nadogradnja školske zgrade s dvorišne strane kako bi se dobile nove učionice i kabineti, što bi omogućilo upravi škole organizaciju nastave u samo jednoj smjeni.

Školske godine 2008./09. škola ima 24 odjeljenja, po 6 prvih, drugih, trećih i četvrtih razreda. Ukupno škola ima oko 740 učenika koji pohađaju tri programa: opći, prirodoslovno-matematički i jezični. U Gimnaziji je uposleno 56 profesora i 12 djelatnika tehničke službe.