Nakon završetka Prvog svjetskog rata u Vinkovcima se sve više raspravljalo o osnivanju nogometnog kluba. Tako je u ljeto 1919. godine u svratištu hotela Slavonija i odlučeno da se isti osnuje i registrira. Na osnivačkoj skupštini za predsjednika je izabran Dr. Đuro Topalović, a diskusija se vodila oko toga da li bi klub trebao biti akademski ili građanski, nogometni ili športski te hoće li se zvati Cibalia ili Graničar. Prevladalo je mišljenje Slavka Jankovića, uz Mišu Zambelija glavnog utemeljitelja osnivačke skupštine i prvog kapetana kluba, pa je osnovan Građanski športski klub Cibalia Vinkovci unutar kojeg su, uz tenis, djelovale i sekcije drugih sportova. Ljubičasti dresovi i bijele gaćice bile su prve klupske boje, a prvo igralište bilo je na Vašarištu. Svoju prvu utakmicu Cibalia je odigrala protiv ŽŠK-a iz Vinkovaca i upisala poraz 2:3.

Od tada Cibalia počinje igrati i sa klubovima iz drugih gradova, a prvi klub kojeg je ugostila bila je Slavija iz Osijeka koja je tada slovila kao najbolji slavonski sastav. Prvo slavlje Cibalia je dočekala protiv ŠK iz Mitrovice kada je upisana više nego uvjerljiva pobjeda 12:0.

GŠK Cibalia i ŽŠK ubrzo su se spojili u Željezničarski građanski športski klub Cibalia, a već 1920. godine osvojen je prvi naslov. Pobjedom u Đakovu nad ŠK Đakovo Cibalia je osvojila naslov Župe. 1921. godine Cibalia je ponovila isti uspjeh, ali stigla i do najvrijednijeg naslova, onog prvaka provincije Zagrebačkog nogometnog podsaveza u kojem su se natjecale momčadi od Zemuna do Zagreba.

U to vrijeme boje Cibalije branili su, među ostalima, Mihajlo Andrejev koji je igrao od osnutka do kraja 30.-ih godina, jedan od najboljih strijelaca stare Cibalije; Mijo Adžić zvani ‘Mujo Bombarder‘ koji je postigao oko 200 golova i u to vrijeme bio jedan od najpopularnijih; Antun Čeh, jedan od najboljih igrača predratne Cibalije; Ferdinand Milhofer koji je bio centarfor, stoper, ali i vratar…

Svoju prvu međunarodnu utakmicu Cibalia je odigrala u rujnu 1930. godine protiv ŠK Pečuh iz Mađarske.

Svibanj 1931. godine ostao je upamćen po tome što je tada otvoreno novo Cibalijino igralište u Lenijama. Novo igralište napravljeno je na terenu Brodske imovne općine koje je Cibalia zakupila na 99 godina. U ljeto 1939. godine izgorjela je drvena tribina na Cibalijinom igralištu, a Uprava kluba predvođena Martinom Balingom brzo je prikupila novčana sredstva za obnovu i izgradnju nove. Godinu dana kasnije Cibalia je kupila i postala vlasnik zemljišta na kojem je bilo igralište.

Sredinom 30.-ih i početkom 40.-ih godina prošlog stoljeća ojačala je Sloga koja je tada uzvratila Cibaliji za ranije poraze. Vinkovci su dobili veliki gradski derbi, dvoboj crno-bijelih(Cibalia) i crveno-bijelih(Sloga), a susrete ovih dvaju klubova u to vrijeme pratilo je više od 1500 gledatelja.
Unatoč ratu i teškim vremenima, nogomet se u Vinkovcima igrao i 1941. godine, a 12. listopada otvorena je nova tribina sa 230 sjedećih mjesta. Tribina je zadržala isti izgled sve do 2009. godine kada ju je vatra u potpunosti progutala.

U 1943. i 1944. godini, zbog ratnih nedaća, momčad se jedva mogla sastaviti. Teško je tada bilo putovati i na gostovanja, a utakmice su se odigravale u prijepodnevnim terminima kako bi se igrači mogli vratiti kući istoga dana. U svibnju 1944. godine, bez obzira na rat, obilježena je 25. godišnjica kluba i tim povodom u Vinkovcima je gostovao Građanski iz Zagreba.

Nakon povlačenja Njemačkih okupacijskih snaga 13. travnja 1945. godine te uspostave nove vlasti, obnavljao se kulturni i športski život u gradu. Svoju prvu sjednicu uprava Cibalije održala je 27. rujna 1945. godine. Na sjednici je riješeno pitanje opstanka i imena kluba. Odlučeno je da naziv bude FD Cibalia. U vrijeme tih događanja u Cibaliji, neposredno po svršetku Drugog svjetskog rata osnovan je i OFD Spartak. Spajanjem ovih dvaju klubova stvoren je FD Graničar, a 25. veljače 1947. godine spajanjem OFD Graničara i Sloge stvoreno je FD Dinamo Vinkovci. U prvoj službenoj utakmici 16. ožujka 1947. Dinamo je na gostovanju u Andrijaševcima ostvario visoku pobjedu 8:1. Te godine Dinamo je osvojio naslov prvaka Nogometnog odbora Slavonski Brod i plasirao se u viši rang natjecanja, Drugu nogometnu zonu Narodne republike Hrvatske.

U sezoni 1948./1949. Dinamo se natječe u Republičkoj ligi, a u kupu se momčad plasirala među 16 najboljih momčadi Jugoslavije. 1951. godine Dinamo se natjecao u Sjevernoj skupini Republičke lige. Iste godine odigrana je i prva međunarodna utakmica protiv Austrijske Herthe. Godine 1952. Dinamo se natjecao u Osječkoj podsaveznoj ligi, 1953. u Jedinstvenoj slavonskoj nogometnoj ligi, a od 1954. godine u novoosnovanoj Podsaveznoj ligi Slavonski Brod kada je osvojio naslov prvaka.

U Trećoj nogometnoj zoni Dinamo je prvi puta nastupao 1955., a potom u sezoni 1957./1958. Početak 1955. godine svakako će ostati upisan i po tome što je za predsjednika kluba izabran Nikola Mika Blažanin koji je tu funkciju obnašao gotovo 2 i pol desetljeća.

Nakon ispadanja iz Treće zone 1958. godine, Dinamo je nastavio natjecanje u novostvorenoj Slavonskoj nogometnoj ligi, potom u ligi nogometnog podsaveza Vinkovci od 1959. do 1960., a od sezone 1960./1961. opet u Slavonskoj ligi u kojoj je do 1967./1968. bio jedna od boljih momčadi.

Još sredinom sada već davne 1961. godine započela je izgradnja stadiona na kojem HNK Cibalia Vinkovci nastupa i danas. Dvije godine kasnije, Vinkovci su dobili objekt koji je bio na ponos  svih građana. Svečano otvorenje održano je 25. svibnja 1963. godine povodom Dana mladosti po kojem i dobiva ime. Pred oko 15.000 ljudi iz grada i okolnih mjesta održan je prigodni program u kojem je sudjelovalo čak 1200 sudionika. Isti dan, reprezentacija Vinkovaca snage je odmjerila s Veležom, a taj susret završio je bez pobjednika – 2:2.

U prvenstvenoj sezoni 1967./1968. Dinamo je postao prvakom Slavonske lige. U doigravanju za Drugu saveznu ligu pobijedio je NK Zadar i NK Orijent i postao član Druge lige. Dinamo je nastupao prvo u sjevernoj, a zatim u zapadnoj skupini Druge lige. Momčad su u početku vodili Tonko Vukušić, Marijan Nosić i Dorđe Mirčetić. Skeleđija, Bručić i Šesto bili su istinski nogometni znalci čijih se poteza i danas vrlo rado sjećaju stariji ljubitelji nogometa.

Dinamo je kao 7. momčad ukinute Druge savezne lige sjever 1973. godine odigrao dvije kvalifikacijske utakmice s NK Rovinj,amaterskim prvakom Hrvatske za mjesto u zapadnoj skupini. U oba susreta Dinamo je pobijedio i postao članom zapadne skupine, ali samo jednu sezonu. Osvojivši naslov prvaka Republičke lige ponovno postaje članom zapadne skupine Druge savezne lige, ovaj puta za duže vrijeme, od 1975./1976. do povijesne sezone 1981./1982.

U natjecateljskoj sezoni 1975./1976. u klub je došla nogometna legenda Dražen Jerković, a njegov dolazak označio je prekretnicu u razvitku kluba. Trener je bio u sezoni 1975./1976., a sportski direktor od 1983. i 1989.

Dužnost trenera u sezoni 1976./1977. preuzeo je poznati nogometni stručnjak Otto Barić. Predsjednikom kluba imenovan je Tomislav Ledić, a Mika Blažanin zaslužio je naziv doživotnog počasnog predsjednika kluba.

1977. godine proslavljena je 30. obljetnica djelovanja NK Dinamo. U srpnju te godine pred 10.000 gledatelja odigrana je utakmica sa Zagrebačkim Dinamom, a nekoliko dana kasnije sa Hajdukom iz Splita. U kolovozu je gostovao i treći prvoligaš, NK Osijek. Te godine stadion je obnovljen, a započeta je i izgradnja dva pomoćna igrališta.

Otto Barić stvarao je Dinamo koji je pod vodstvom Tonka Cice Vukušića ostvario ulazak u Prvu saveznu ligu, najveći uspjeh u dotadašnjoj povijesti kluba. Svima poznati susret s Čelikom odigran je 6. lipnja 1982. godine pred 15.000 gledatelja. Osim trostrukog strijelca Sulejmana Halilovića, gostujuću mrežu pogađali su još Nenad Lušić i Ivica Tunjić. Za momčad koja je ostvarila taj uspjeh nastupili su Tomislav Radić, Stevo Bogdan, Branko Mlinar, Svetozar Mirosavljević, Ilija Radić, Dušan Kesić, Nedan i Srećko Lušić, Ivica Tunjić, Milorad Rajović i Sulejman Halilović. Upravo za ovoga posljednjeg stručnjaci, ali i laici tvrde da je najbolji igrač u povijesti Dinama, odnosno Cibalije. Bio je najbolji strijelac prvenstva u Drugoj ligi u više navrata, a u sezoni 1982./1983. i u Prvoj ligi. Iz drugoligaškog Dinama dospio je i do reprezentacije, a prema izboru kapetana prvoligaša i sportskih novinara proglašen je i najboljim igračem lige. U magazinu Tempo osvajač je tada najveće nagrade Zlatna kopačka.

U prvoligaškoj konkurenciji Dinamo je nastupao pet sezona.

5. listopada 1990. godine klub se vratio svojim korijenima i starom imenu Cibalia. Formiranjem Hrvatske nogometne lige, Cibalia je na temelju ranijih uspjeha bila član prvoligaškog društva i 28. veljače 1992. godine protiv HAŠK-a na Maksimiru odigrala prvu i povijesnu utakmicu u Hrvatskoj nogometnoj ligi.

Pred 6.000 gledatelja rezultatom 2:0 slavio je domaćin, a našu momčad s kupe je vodio Mile Petković sa svojim pomoćnikom Stankom Mršićem. Nastupili su Mrmić, Perišić, Jozinović, Zahirović, Raguž, Goran i Mario Meštrović, Halilović, Plavšić, Čop i Markovinović. Zbog opasnosti i učestalog granatiranja Vinkovaca, Cibalia te sezone niti jednu utakmicu nije odigrala u svom gradu, već je domaćin bila pet puta u Đakovu, četiri puta u Požegi te jednom u Zagrebu i Čakovcu. Prvi pogodak Cibalije u HNL-u postigao je Goran Meštrović, a prva pobjeda upisana je u šestom kolu protiv Varteksa.

Krajem sezone  1996./1997. Cibalia je prvi put napustila prvoligaško društvo. Na sreću i radost svih navijača, samo na jednu sezonu. Dvije sezone kasnije momčad je stigla do finala Hrvatskog nogometnog kupa. Protivnik je tada bio Osijek, a susret je odigran na Maksimiru 30. svibnja 1999. godine. Jure Jurić je nebeskoplave doveo u vodstvo koje se držalo sve do posljednih sekunda. Osječani tada izjednačuju, a u produžecima Cibalia s dva igrača manje više nije imala izgleda.Nakon toga, Cibalia je prvi put nastupila u jednom europskom natjecanju – Intertoto kupu. Pred ispunjenim tribinama vinkovačkog stadiona s tri pogotka ispraćen je beogradski Obilić, uzvrat je završio bez pobjednika(1:1), a sljedeći protivnik bila je mađarska Tatabanya koja je bila sretnija pa tek u drugom susretu pogotkom u posljednjim minutama izborila prolazak u sljedeću fazu natjecanja.

Drugi nastup u Intertoto kupu Cibalia je upisala u sezoni 2003./2004. Uspješniji su nebeskoplavi bili od bjeloruskog Šahtara iz Soligorska te finskog Tamperea, ali pretežak protivnik bio je bundesligaš Wolfsburg koji je u polufinalu bio bolji s ukupnih 8:1.

Malo se tko nadao da bi se to moglo dogoditi, ali već iduće sezone Cibalia je ponovno bila drugoligaš. Kao i prvi put, pokazala je kako joj tamo nije mjesto i ekspresno se, nakon velike dominacije i unatoč oduzimanju bodova, vratila u društvo najboljih. U dvije kvalifikacijske utakmice svladana je Novalja ukupnim rezultatom 5:1.

2008. i 2010. stadion u Vinkovcima nakon dugog niza godina doživio je prve ozbiljnije zahvate. Gledatelji su tako dobili priliku pratiti utakmice pod reflektorima, a stadion je dobio i novu atletsku stazu, na istočnoj i zapadnoj tribini postavljene su nove sjedalice, stigle su nove klupe za pričuvne igrače, uređena je VIP loža te postavljen novi semafor na južnoj tribini.

2008. godine klub je proslavio 90. obljetnicu svog postojanja, a sve je uveličala reprezentacija Hrvatske koja je prvi put odigrala jedan susret u Vinkovcima. 14. listopada protiv Lihtenštajna je upisana visoka pobjeda, a susret su pratile ispunjene tribine vinkovačkog stadiona.

U sezoni 2009./2010. Cibalia je ostvarila svoj najveći uspjeh. Igrači vođeni trenerom Stankom Mršićem sezonu su završili kao trećeplasirani sa samo pet bodova zaostatka za prvakom Dinamom, iako bi pobjeda u posljednjem kolu u Osijeku donijela i drugo mjesto. Taj uspjeh značio je novi izlazak na europsku scenu, ali ovog puta u kvalifikacijama za Europsku ligu. Cibalijin protivnik bio je Cliftonville, predstavnik Sjeverne Irske koji je priredio iznenađenje i zaustavio nebeskoplave već na prvom koraku.

2011. godine klub je krenuo u preoblikovanje nakon kojeg je Cibalia postala športsko dioničko društvo, a većinski vlasnik bio je Grad Vinkovci.

Na kraju sezone 2012./2013. Cibalia je treći put ispala iz svog starog društva, iako je samo mjesec dana ranije igrala i polufinale Hrvatskog nogometnog kupa. Ovog puta bilo je puno teže pa se nakon neuspješnih kvalifikacija sa Slaven Belupom povratak među prvoligaše čekao još dvije sezone. Čak 11 bodova zaostatka za Šibenikom nadoknadila je tada Cibalia i svoj prvoligaški status potvrdila u posljednjem kolu u izravnom dvoboju na Šubićevcu. Taj uspjeh proslavljen je četiri dana kasnije, 25. svibnja 2016. godine na gradskom korzu u Vinkovcima.