Herceg Novi, İtalyanca olarak Castelnuovo; adından anlaşıldığının aksine yeni değildir, oldukça eski sayılmaktadır. Şehir, günümüzde merkezdeki meydanın adını taşıdığı Bosna Kralı I. Stephan tarafından, bir balıkçı köyünün bulunduğu yerde 1382 yıllında kurulmuştur. Türkler şehri 1482’de fethediyorlar ve iki yüzyıl boyunca burada kalıyorlar, sadece şehir İspanyoların altındayken küçük bir kesinti yaşanıyor. Herceg Novi 1687 yılında Venedik, sonra Avusturya-Macaristan İmparatorluğu’nun eline geçiyor, daha sonra Napoleon, Ruslar, sonra Mussolini’nin altında kalıyor, daha sonra Yugoslavya’nın bir parçası oluyor. Tarihinin, hepsi olmasa da, meydanda bulunabilir. Paradoksal bir meydandır, çünkü palmiye ağaçları ile çevrili muhteşem bir Ortodoks kilisesi olan bir İtalyan türü meydandır. Gayri resmi olarak, meydanın ismi Belavista’dır. Buradan deniz, bir Osmanlı saat kulesi, İspanyol kalesi, Katolik kilisesinin kampı ve alttaki şehrin manzarası görürebilir.
