Археолошки налази из пећине Врањај  и са полуострва Луштица, свједоче о зачецима цивилизације на овим просторима још у неолиту и раном бронзаном добу. Пећина Врањај налази се у масиву планине Орјен изнад извора Диздарица и данас је најстарије археолошко налазиште из праисторије херцегновског краја и открива простор на којем се преплићу културе праисторијских фаза.

У III вијеку нове ере, послије побједе над Илирима, овим крајевима је завладала Римска империја.
Након пропасти западног римског царства 476. године, овим крајевима доминира Византија. Словенска племена доста густо насељавају ове просторе у VII вијеку, у периоду када на тлу Византије ничу прве државе - жупе, у почетку зависне од Византије, а касније постепено стичу независност и политичку аутономију. На простору око данашњег Херцег-Новог формира се Жупа Драчевица. Већ од X вијека Драчевица губи независност, постаје плијен зетских кнежева, али не задуго јер слиједи период Немањића. Послије смрти цара Душана, Драчевицом, за кратко, влада кнез Војислав Војновић, а затим Балшићи.
У жељи да Босна добије излаз на море и да се емнципује од дубровачке луке,  босански краљ Твртко И Котроманић заузима Драчевицу 1378. године. На брежуљку утврђује нови град 1382. године с намјером да га развија као значајан трговачки, поморски и занатски центар и даје му име Свети Стјепан. Као један од најмлађих градова на Јадрану називају га и Нови, Каструм Новум, Кастел Нуово.
Своје данашње име добио је у вријеме владавине Херцег Стјепана Вукчића Косаче, када је доживио највећи процват и развој. Долази до снажног развоја оружарских, златарских, ковачких и обућарских заната. Из тог су периода сачувани значајни примјерци златарског умијећа који се чувају у Ризници Манастира Савина.

	Povelja kralja Tvrtka I od 2.12.1382. god.		Tvrtko I na bareljefu vajara Afrana Hodžića

Херцег Стјепана наслеђује његов син Влатко, али упркос снажном отпору не успијева да одоли турској војсци која Нови осваја 1482. године.
Турским освајањем почиње нови период историје Херцег-Новог. Турци предузимају опсежне радове на утврђењу града. Има доста индиција да је тада саграђена тврђава Шпањола која доминира градом и околним простором.
Флота шпанског адмирала Андреа Дорије изненада је стигла под Херцег Нови јуна 1538. године. Сутрадан су Турци предали град Шпанцима, који су ту оставили посаду од 6000 људи. Уочивши значај утврђења које доминира градом на највишој коти, Шпанци су одмах започеви поправку бедема и тог утврђења. Међу локалним становништвом, утврђење је добило име Шпањола, иако се у највећем броју докумената оно назива Горњи град. Само девет мјесеци касније, у јулу 1539. године, турски адмирал Хајредин Барбароса са огромном флотом осваја град, послије дуге и тешке борбе. Према свједочењу путописца Евлије Челебића, који је Херцег-Нови посјетио 1664. године, град је свратиште, уточиште и спремиште страних гусара, као и транзитно мјесто за трговину робљем.
Земљотрес који 1667. године посебно погодио Дубровник, донио је велика разарања и Херцег-Новом. Исте године Турци приступају обнови града, међутим осјећа се све већи притисак Млетачке Републике и њених савезника да се Херцег Нови врати у хришћанске руке.
Након 30 дана жестоких борби, 30. септембар 1687. године, након два вијека турске владавине, град отимају Млечани на челу са војсковођом Јеронимом Корнером и одмах прилазе реконструкцији порушених утврђења.
Млечани владају све до пропасти Млетачке Републике 1797. године. Од тада долази до честих промјена управе у Херцег-Новом.
Аустријанци су владали до 1806. године. У то доба, Херцег-Нови је од првобитне трговачке функције, сада преузео улогу стратегијске одбране улаза у Боку Которску, што је историја касније потврђивала.
Након тога, власт преузимају Руси до 1807. године, а потом Французи. Дана 14. октобра 1813. године Бокељи и Црногорци, потпомогнути с мора Енглезима, заузимају Нови и држе га све до 6. јуна 1814. године када га је заузела аустријска војска, послије велике и тешке борбе.

До 1918. године град је био под Аустроугарском управом. Затим долази до уједињења Срба, Хрвата и Словенаца у Краљевину, односно нешто касније у Југославију. Након капитулације Југославије 1941. године у граду су као окупатори били Италијани, а затим и Њемци. Херцег-Нови је ослобођен, 28. октобра 1944. године и тај датум се данас слави као Дан ослобођења града и Празник града.

Панорама града