Ideja o osnivanju nogometnog kluba u Vinkovcima nastala je još na samom početku 20. stoljeća. Sve je, međutim, za neka bolja vremena odgodio Prvi svjetski rat. Ideja je opstala i po završetku rata, a isti ljudi, predvođeni Slavkom Jankovićem, okupili su se 7. svibnja 1919. godine u svratištu hotela Slavonija i odlučili da se klub osnuje i registrira. Na osnivačkoj skupštini za predsjednika je izabran Dr. Đuro Topalović, a diskusija se vodila oko toga hoće li klub 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. Prvi dresovi bili su ljubičasti, a gaćice bijele, iako su prve klupske boje bile crna i bijela. Drugih dresova, osim ljubičastih, u tom trenutku jednostavno nisu imali. Prvo igralište Cibalije bilo je na Vašarištu, a 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.
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. Ubrzo, GŠK Cibalia i ŽŠK fuzionirani su u Željezničarski građanski športski klub Cibalia.
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 godina prošlog stoljeća ojačala je Sloga koja je tada uzvraćala
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 tisuću gledatelja.
Unatoč Drugom svjetskom ratu i teškim vremenima, nogomet se u Vinkovcima igrao i 1941. godine. 12. listopada otvorena je tako nova tribina sa 230 sjedećih mjesta koja 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, a teško je tada bilo i putovati na gostovanja. Utakmice su se odigravale u prijepodnevnim terminima kako bi se igrači mogli vratiti kući istoga dana. U svibnju 1944. godine, unatoč ratnim nedaćama, 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. Vodila se velika borba za opstanak imena kluba, a u vrijeme tih događanja, neposredno po svršetku Drugog svjetskog rata, osnovan je i OFD Spartak. Spajanjem ovih dvaju klubova stvoreno je FD Graničar, a 25. veljače 1947. godine spajanjem Graničara i Sloge nastaje je FD Dinamo Vinkovci.
U sezoni 1948./1949. Dinamo se natjecao u Republičkoj ligi, a u kupu se momčad plasirala među 16 najboljih momčadi Jugoslavije. Od 1952. Dinamo se natjecao u Osječkoj podsaveznoj ligi, od 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 godina je ostala upisana i po tome što je za predsjednika kluba izabran Nikola Mika Blažanin koji je tu funkciju obnašao gotovo dva i pol desetljeća.
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. 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 12.000 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.
Kao 7. momčad ukinute Druge savezne lige sjever Dinamo je 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čela 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.
Nakon dugog niza godina, 2008. i 2010. godine, prve ozbiljnije zahvate doživio je stadion u Vinkovcima. 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. 2018. godine dočekana su nova uređenja, a povod je bila finalna utakmica Hrvatskog nogometnog kupa kada su u Vinkovcima snage odmjerila dva najbolja Hrvatska kluba – Dinamo i Hajduk.
2009. 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. To, nažalost, nije donijelo značajnije pomake u poslovanju kluba pa je Cibalia na kraju sezone 2012./2013. 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. Uspjeh je proslavljen 25. svibnja 2016. godine na gradskom korzu u Vinkovcima.
Na osnovu ostvarenog rezultata klub je na kraju sezone 2017./2018. napustio prvoligaše, ali zbog financijskih problema i nedobivanja licence za taj rang natjecanja odlazi među trećeligaše. Uspješno i uvjerljivo je apsolvirana trećeligaška sezona 2018./2019., a u svibnju 2019. proslavljena je i 100. obljetnica osnutka kluba.
