Život mesta a jeho dejiny boli odjakživa ovplyvňované jeho polohou a prírodnými podmienkami. Priaznivé okolnosti, najmä blízkosť rieky Bodvy, úrodná pôda, relatívne chránená dolina z hľadiska podnebia, ako aj výhodná poloha mesta na obchodných trasách zo severu na juh a z východu na západ, znamenali pre Moldavu často aj vojenské ohrozenie. Archeologické nálezy potvrdzujú predpoklad, že toto územie si vybral za svoje bydlisko už pračlovek. Blízke jaskyne krasu mu poskytovali ochranu pred divou zverou, pred zimou a pred nepriateľmi.
Po príchode maďarských kmeňov sa na tomto území usadili príslušníci chazarsko-kabarského kmeňa Abovcov a rodu Bárca-Tekele. Prvá písomná zmienka o meste je z roku 1255. Ide o listinu, ktorá potvrdzuje majetkový stav okolia z roku 1150. O vydanie tohto dokumentu požiadal jasovský kláštor, lebo pôvodná listina bola počas tatárskeho vpádu zničená. Moldava bola v tomto období súčasťou turnianskeho hradného panstva a patrila medzi kráľovské majetky. Pôvodné pomenovanie bolo „villa curriferorum ZEKERES“ (Vozokany), ktoré označuje povolanie pôvodných obyvateľov zaoberajúcich sa povozníctvom. Už v roku 1267 sa názov uvádza ako SCEPSY-SCEKERES. Tradícia a literatúra potvrdzujú, že sa tieto formy názvu už vtedy vyslovovali „sepši“ resp. „sepši-sekereš“. V roku 1329 sa po prvý raz objavuje nemecké pomenovanie „MOLDAVA“, ktoré sa vzťahuje tak na rieku Bodva ako aj na osadu (Bolda, Polda, Molda sú názvy zaužívané nemeckými kolonistami na označenie rieky Bodva). Keďže od 15. storočia sa ešte ako súbežné pomenovanie zachovalo aj Szekeres – Szekeresfalva, mnohí sa domnievajú, že popri starom meste po vpáde Tatárov vzniklo aj novšie, v ktorom sa usadili aj nemeckí prisťahovalci, zaoberajúci sa poväčšine klčovaním okolitých lesov.
V roku 1927 bolo mesto úradne nazvané „Moldava nad Bodvou“. Významným dokumentom je menovacia listina kráľovského sokoliara Leonarda z Moldavy, ktorú podpísal kráľ Ladislav IV. Kumánsky (1272-1290) pri príležitosti svojho pobytu v Moldave. Spis je datovaný 30. marca 1282 a je najstarším zachovaným dokumentom vystaveným na území mesta. Správy o kostole potvrdzujú, že už pred rokom 1290 stál v Moldave murovaný kostol. Ten bol v 15. storočí za vlády kráľa Mateja Korvína (1458-1490) prestavaný (v rovnakom období dostal svoju konečnú podobu aj košický Dóm svätej Alžbety. O podobnosti štýlu svedčí južný portál, ktorý nesie aj znaky príbuznosti s južným portálom rožňavského farského kostola). Pôvodne bol moldavský kostol trojloďový. Kostol niekoľkokrát vyhorel – r. 1644, r. 1794, zreštaurovaný bol v rokoch 1646, po r. 1794, r. 1895-1896, r. 1935 a po druhej svetovej vojne. Katolícka fara je klasická. Pochádza z konca 18. storočia. Kostol reformovanej cirkvi z r. 1773 je postavený v klasickom štýle. Veža bola dostavaná r. 1789 a kostol bol obnovovaný koncom 18. storočia a v rokoch 1876, 1922, 1951 a 1997. Pečatidlo (typárium) mesta je vyrobené v 17. storočí. Je na ňom holubica s roztvorenými krídlami symbolizujúca Ducha Svätého. Okolo holubice je oválny nápis: SIGILLUM OPPIDUM SEPSIENSIS. Rozvoju mesta prispela historická udalosť v 14. storočí, keď Košice podporili Anjouovcov v boji s Omodejovcami a za to im kráľ Karol Róbert (1308-1342) a jeho syn Ľudovít I. Veľký (1342-1382) udelil mnohé výsady, medzi nimi aj právo vyberať od kupcov vysoké mýta a dane. Mnohí obchodníci na to reagovali tak, že obišli Košice a cestu na sever hľadali cez Moldavu. V tomto storočí sa v Moldave vybudoval rozsiahly pivničný systém, ktorý sa využíval na skladovanie tovaru – najmä ovocia a vína. Rozšírilo sa pestovanie viniča, príprava vlastného vína, hrnčiarstvo a niektoré ďalšie remeslá. Z roku 1317 je zaznamenané, že Moldavu riadila „mestská rada na čele s richtárom“.
V roku 1458 mala už Moldava svoju školu, remeselnícke cechy, napr. cech kolesárov, čižmárov, zámočníkov, mäsiarov, krajčírov, remenárov, obchodníkov s vínom a pod. Na rozvoj mesta zvlášť nepriaznivo pôsobili vojnové roky. Počas vojen sa obchod zanedbával, armáda spotrebovala zásoby obyvateľstva a pod. V 15. storočí vypukli nepokoje súvisiace s bojom o uhorský trón. Kráľovná Alžbeta, vdova po zosnulom kráľovi Albertovi Habsburskom (1438-1439), na podporu práv svojho syna Ladislava Pohrobka (1444-1457) voči Vladislavovi I. (1440-1444) privolala českého žoldniera Jána Jiskru z Brandýsa. Ten okrem ďalších miest a hradov obsadil aj Moldavu. V roku 1526 v bitke pri Moháči padol aj zemepán Moldavy Štefan Rozgonyi.Do roku 1532 klesol počet domácností v Moldave na 60. V roku 1553 sa opäť spomína trhové právo Moldavy. Trhy sa konali 10. júna na deň svätej Margity a neskôr až štyrikrát do roka.
Počas tureckej nadvlády sa Moldava do rúk sultána nedostala, ale jágerskému pašovi platila pravidelné dane: 260 zlatých toliarov v čase mieru a 60 zlatých toliarov v čase vojen- čím si mesto kúpilo výsadu, aby Turci nevkročili do opevneného mesta.
V roku 1564 bol zemepánom Moldavy András Báthory, dane sa odvádzali za 90 dvorov. Je to obdobie začiatku reformácie.
Takmer celé mesto prešlo na novú, kalvínsku vieru. Ovplyvnil to hlavne zvyk nasledovať aj vo vyznaní svojho zemepána.
Bohatí zemepáni a mešťania považovali za svoju povinnosť podporovať nadaných mladých ľudí v ich štúdiách, a to aj v zahraničí. Do tridsaťročnej vojny sa registrovalo niekoľko desiatok moldavských študentov na západoeurópskych školách a univerzitách. Z nich spomeňme len najslávnejších – Györgya Korotza, Mátého Szepsi Laczkó, Mártona Szepsi Csombora a i.
V roku 1602 mala už Moldava „triviálnu“ školu. V roku 1590 sa v blízkej maďarskej obci Gönc pod vedením Gašpara Károlyiho dokončil prvý maďarský preklad Písma, na ktorom spolupracoval aj vtedajší moldavský duchovný. Dielo bolo vytlačené vo Vizsolyi na území dnešného Maďarska.
V roku 1620 spomína rodák Márton Szepsi Csombor Moldavu ako mesto chránené hradbami. Hradby boli potrebné, veď išlo o turecké časy a navyše, ako to stojí v kráľovskej listine z roku 1571, „…kráľovské vojská by mali chrániť Moldavu tak pred Turkom, ako aj pred prechmatmi bohatých zemepánov…".
V polovici 90-tych rokov 16. storočia sa skoro celá Moldava stala obeťou požiaru. Prežil iba kamenný kostol. Škody boli rýchlo odstránené a mesto opäť ožilo.
Z roku 1629 pochádzajú výsady pre mesto od panovníka – Ferdinanda II. (1619 – 1637). Význanmnú úlohu v protireformácii zohral františkánsky páter Herko, ktorého dodnes spomínajú ako Herkopáter. Zachovala sa aj jeho podobizeň vtesaná do kameňa, ktorá je umiestnená v r. k. kostole s vyznačením roku jeho smrti (1686). Kroniky zaznamenali, že protestantov „presviedčal“ nevyberaným spôsobom, často na čele vojakov a so sekerou v ruke.
26. novembra 1683 sa pri Moldave zastavil poľský kráľ Jan III. Sobiesky (1674 – 1686), ktorý sa na čele víťazného vojska vracal spod Viedne, kde spolu so svojimi spojencami porazil turecké vojská. Bol to začiatok oslobodzovania územia spod tureckej nadvlády trvajúcej vyše sto rokov. V Moldave prijali kráľa s náležitou úctou a slávou.
Rok 1711 bol pre mesto nepriaznivý. Moldava musela ubytovať a stravovať po dobu pol roka 3000 cisárskych vojakov. Po vojakoch prišla epidémia. V roku 1715 zaznamenali, že zo 180 domov v meste ostalo obývaných iba 44.
Počas panovania Márie Terézie (1740 – 1780), v roku 1772, dostali moldavskí protestanti povolenie vybudovať kostol bez veže. Tento kostol sa o dva roky zrútil a bol obnovený až v roku 1789 (dodnes stojí na námestí). Keďže náboženské nepokoje neustávali, obe strany – katolícka a kalvínska – sa v roku 1793 dohodli, že v mestskej rade budú zastúpené v rovnakom pomere. V Moldave sa mestská rada volila na 3 roky. Richtára (starostu) na rok – striedavo z oboch vyznaní. Mestský notár bol vždy opačného vyznania, než bol richtár.
28. augusta 1794 mesto opäť zhorelo. Obeťou požiaru sa stala aj päťtisíczväzková knižnica. Tragédia sa neobišla bez ľudských obetí. Okrem kostolov, ktoré zostali bez strechy, sa pred požiarom uchránila iba tzv. Szojkova drevená brána, na ktorú potom v latinčine vyryli nápis Plameňom som horela a predsa som nezhorela. Táto brána sa dnes nachádza na dvore múzea v Košiciach a jej kópia pri ref. kostole v Moldave nad Bodvou bola odhalená v roku 1996.
Históriu mesta v 19. storočí silne ovplyvňovala blízkosť Košíc, mesta, ktoré bolo po Budíne druhým najvýznamnejším mestom starého Uhorska.
V roku 1813 postihla mesto povodeň. V roku 1828 bolo zaznamenaných 278 domov a 2281 obyvateľov. O tri roky neskôr v morovej epidémii prišlo o život 212 občanov. Na pamiatku tejto tragickej udalosti postavili pozostalí na úbočí moldavského kopca kaplnku sv. Rócha. Ďalšia morová epidémia v roku 1872 si vyžiadala 34 obetí. V roku 1868 sa začala železničná doprava do Košíc a v roku 1894 aj do Medzeva.
V roku 1901 dostavali budovu školy (dnešná špeciálna škola). V meste vyvíjali činnosť dve tlačiarne, kasíno a čitateľský spolok. Rozvoj však narušila prvá svetová vojna. Po vzniku Československa mala Moldava v roku 1920 už 2176 obyvateľov, v rokoch druhej svetovej vojny 2,5 tisíc.
Vo vojne mesto zaznamenalo úbytok približne 200 obyvateľov židovského pôvodu. Prvé povojnové roky boli poznamenané aj násilným odvlečením obyvateľstva do pracovných táborov v Sovietskom zväze. Vojna zanechala stopy aj na budovách.
Ďalší rozvoj nastal až po začatí výstavby VSŽ, kedy sa na pravom brehu rieky začala hromadná bytová výstavba. Počet obyvateľov vzrastal a zmenilo sa aj jeho národnostné zloženie. Neskôr boli k Moldave pričlenené susedné obce Mokrance a Budulov, Mokrance sa v roku 1990 opäť odčlenili.
Posledné roky sú charakteristické zveľaďovaním mesta, opravou komunikácií, rekonštrukciou historického jadra mesta. Zaviedla sa káblová televízia, zakladajú sa nové kultúrne tradície. V starej kováčskej dielni bolo vytvorené mestské múzeum.