NK "Croatia" rođena je 6. lipnja 1972. godine, kad je registriran nogometni klub iz Orehovice pod imenom NK "Croatia" Orehovica kod tadašnje Stanice javne sigurnosti u Čakovcu. Tada je prihvaćen Statut i ime kluba. Osnivačka skupština inicirana od strane mještana s glavnim inicijatorom Ivanom Baranićem, održana je nešto ranije, 14. svibnja 1972. godine.
Inicijativa za nogometnim klubom i imenom krenula je zapravo godinu dana ranije. Međutim, zbog tadašnje teške političke situacije u Hrvatskoj, te obračuna tadašnjih jugoslavenskih vlasti sa svime što je imalo hrvatski predznak, bilo je vrlo komplicirano osnovati klub tog imena. Pojedini ljudi imali su zbog toga i dosta neugodnosti, često su pozivani na "informativne razgovore", samo s jednim pitanjem: Zašto baš Croatia!? Naime, tada se željelo nametnuti neko drugo ime, ali nakon povuci-potegni, vlast je nakon godinu dana natezanja ipak popustila i registrirala klub. Prema dostupnim podacima NK Croatia Orehovica drugi je klub u Hrvatskoj koji je dobio ime Croatia. Prije NK "Croatia" Orehovica, osnovan je samo jedan klub pod tim imenom u Hrvatskoj - NK Croatia Đakovo. Tek nakon toga i veliki broj drugih nogometnih kluba izabrao je hrvatsko ime, a među posljednjima i NK Croatia Zagreb. Međutim, za razliku od mnogih drugih Croatia, pa i zagrebačke čije je opet ime promijenjeno u NK Dinamo, NK Croatia Orehovica nikad u svojoj povijesti usprkos mnobrojnim političkim i policijskim pritiscima nije mijenjala ime.
Kroz proteklih godina u radu kluba sudjelovao je veliki broj ljudi. Prvo vodstvo NK Croatia dobila je na osnivačkoj skupštini. Za prvog predsjednika izabran je tadašnji ravnatelj Doma umirovljenika Orehovica Franjo Levak. Tajničku dužnost obnašao je Maks Bali, a blagajničku Josip Šafarić. Kroz godine koje su uslijedile veliki broj mještana Orehovice radio je u klubu. Nažalost, neki od njih u međuvremenu su i umrli, ali tradicija Croatie ostaje neuništiva. Najodgovornije funkcije u klubu tijekom proteklih godina obnašali su: Stjepan Peršić, Stjepan Kamenić, Ivan Piknjač, Franjo Držanić, Dragutin Debelec, Željko Martinec, Damir Poljanec, Ladislav Požgaj, Franjo Piknjač te Željko Vurušić (sadašnji) kao predsjednici; Josip Ružić, Franjo Mađarić, Josip Šafarić, Vlado Matjašec, Dragutin Debelec te Alen Ružić, kao tajnici; Anđelko Košak, August Kodba, Franjo Drvenkar, Stjepan Farkaš, Josip Čurin, Franjo Piknjač, Zdravko Cvrtnjak, Franjo Markač, Antun Požgaj, Vurušć Željko, Goran Plaftak kao blagajnici. Još niz drugih mještana Orehovice bili su članovi uprave kluba, a veliki broj mještana aktivan je i danas.
U radu kluba najveća akcija provedena je od 1980. do 1982. godine kada se gradilo novo igralište. Za te godine vezana je i jedna ne baš lijepa uspomena. Naime, od tadašnjeg vodstva MZ Orehovica stiglo je obećanje da će se staro igralište zamijeniti za novo. Na starom igralištu izgrađena je poslovna zgrada, a novo MZ nije izgradila, te je klub bio izigran i prepušten sam sebi. Novo igralište ipak se izgradilo, zahvaljujući susretljivosti ljudi koji su radili na izgradnji hidrocentrale, tako da je ispalo da su oni imali više sluha za rješavanje tog problema, nego tadašnje vodstvo MZ. Tijekom 1984. godine klub je opet imao problema s bivšom vlasti, kada su klupske zastavice proglašene ustaškima. Ipak, srećom, sve je to danas prošlost, na koju su usprkos svim problemima mnogi od ljudi koji su svih ovih godina radili u klubu ponosni, posebice danas, odnosno proteklih godina kada je u nekim sredinama nošenje imena Croatia postao pomodarski trend. Naime, NK Croatia Orehovica ipak je klub s jednom od najdužih tradicija nošenja imena Croatia u Hrvatskoj.
Ipak, najvažniji su rezultati koji je klub postigao na sportskom polju. Najveći uspjeh kluba je plasman u polufinale Kupa NSM-a u kojem je eliminiran od tada najjačeg međimurskog kluba čakovečkog MTČ-a. U dva navrata NK Croatia plasirala se u najbolju međimursku ligu. Prvi put na 15. godišnjicu postojanja 1987. godine u I. međimursku ligu, a drugi put 2002. pod vodstvom trenera Josipa Piskać u IV HNL.