Arheološki nalazi iz pećine Vranjaj  i sa poluostrva Luštica, svjedoče o začecima civilizacije na ovim prostorima još u neolitu i ranom bronzanom dobu. Pećina Vranjaj nalazi se u masivu planine Orjen iznad izvora Dizdarica i danas je najstarije arheološko nalazište iz praistorije hercegnovskog kraja i otkriva prostor na kojem se prepliću kulture praistorijskih faza.

   

Sudovi iz pećine Vranjaj-eneolit, bronzano doba, 1700-800 g.p.n.e

U III vijeku nove ere, poslije pobjede nad Ilirima, ovim krajevima je zavladala Rimska imperija.

Nakon propasti zapadnog rimskog carstva 476. godine, ovim krajevima dominira Vizantija. Slovenska plemena dosta gusto naseljavaju ove prostore u VII vijeku, u periodu kada na tlu Vizantije niču prve države - župe, u početku zavisne od Vizantije, a kasnije postepeno stiču nezavisnost i političku autonomiju. Na prostoru oko današnjeg Herceg-Novog formira se Župa Dračevica. Već od X vijeka Dračevica gubi nezavisnost, postaje plijen zetskih kneževa, ali ne zadugo jer slijedi period Nemanjića. Poslije smrti cara Dušana, Dračevicom, za kratko, vlada knez Vojislav Vojnović, a zatim Balšići.
U želji da Bosna dobije izlaz na more i da se emncipuje od dubrovačke luke,  bosanski kralj Tvrtko I Kotromanić zauzima Dračevicu 1378. godine. Na brežuljku utvrđuje novi grad 1382. godine s namjerom da ga razvija kao značajan trgovački, pomorski i zanatski centar i daje mu ime Sveti Stjepan. Kao jedan od najmlađih gradova na Jadranu nazivaju ga i Novi, Kastrum Novum, Kastel Nuovo.
Svoje današnje ime dobio je u vrijeme vladavine Herceg Stjepana Vukčića Kosače, kada je doživio najveći procvat i razvoj. Dolazi do snažnog razvoja oružarskih, zlatarskih, kovačkih i obućarskih zanata. Iz tog su perioda sačuvani značajni primjerci zlatarskog umijeća koji se čuvaju u Riznici Manastira Savina.
 
                                     
 

Povelja kralja Tvrtka I od 2.12.1382. god.

  Tvrtko I na
bareljefu vajara Afrana Hodžića
Herceg Stjepana nasleđuje njegov sin Vlatko, ali uprkos snažnom otporu ne uspijeva da odoli turskoj vojsci koja Novi osvaja 1482. godine.
Turskim osvajanjem počinje novi period istorije Herceg-Novog. Turci preduzimaju opsežne radove na utvrđenju grada. Ima dosta indicija da je tada sagrađena tvrđava Španjola koja dominira gradom i okolnim prostorom.
Flota španskog admirala Andrea Dorije iznenada je stigla pod Herceg Novi juna 1538. godine. Sutradan su Turci predali grad Špancima, koji su tu ostavili posadu od 6000 ljudi. Uočivši značaj utvrđenja koje dominira gradom na najvišoj koti, Španci su odmah započevi popravku bedema i tog utvrđenja. Među lokalnim stanovništvom, utvrđenje je dobilo ime Španjola, iako se u najvećem broju dokumenata ono naziva Gornji grad. Samo devet mjeseci kasnije, u julu 1539. godine, turski admiral Hajredin Barbarosa sa ogromnom flotom osvaja grad, poslije duge i teške borbe. Prema svjedočenju putopisca Evlije Čelebića, koji je Herceg-Novi posjetio 1664. godine, grad je svratište, utočište i spremište stranih gusara, kao i tranzitno mjesto za trgovinu robljem.
Zemljotres koji 1667. godine posebno pogodio Dubrovnik, donio je velika razaranja i Herceg-Novom. Iste godine Turci pristupaju obnovi grada, međutim osjeća se sve veći pritisak Mletačke Republike i njenih saveznika da se Herceg Novi vrati u hrišćanske ruke.
Nakon 30 dana žestokih borbi, 30. septembar 1687. godine, nakon dva vijeka turske vladavine, grad otimaju Mlečani na čelu sa vojskovođom Jeronimom Kornerom i odmah prilaze rekonstrukciji porušenih utvrđenja.
Mlečani vladaju sve do propasti Mletačke Republike 1797. godine. Od tada dolazi do čestih promjena uprave u Herceg-Novom.
Austrijanci su vladali do 1806. godine. U to doba, Herceg-Novi je od prvobitne trgovačke funkcije, sada preuzeo ulogu strategijske odbrane ulaza u Boku Kotorsku, što je istorija kasnije potvrđivala.
Nakon toga, vlast preuzimaju Rusi do 1807. godine, a potom Francuzi. Dana 14. oktobra 1813. godine Bokelji i Crnogorci, potpomognuti s mora Englezima, zauzimaju Novi i drže ga sve do 6. juna 1814. godine kada ga je zauzela austrijska vojska, poslije velike i teške borbe.

Do 1918. godine grad je bio pod Austrougarskom upravom. Zatim dolazi do ujedinjenja Srba, Hrvata i Slovenaca u Kraljevinu, odnosno nešto kasnije u Jugoslaviju. Nakon kapitulacije Jugoslavije 1941. godine u gradu su kao okupatori bili Italijani, a zatim i Njemci. Herceg-Novi je oslobođen, 28. oktobra 1944. godine i taj datum se danas slavi kao Dan oslobođenja grada i Praznik grada.

Panorama grada