Novi Grad se prvi put u dokumentima pominje 1217. godine, mada se historičari priklanjaju mišljenju da je grad osnovan 1280. godine.
Šire područje grada bilo je naseljeno još u antičko doba o čemu svjedoče Arheološka nalazišta u selu Donji Rakani i u dolini rječice Japre.
Prvo naselje nije moglo nastati na današnjem Gradskom području jer bilo je izloženo plavljenju rijeka Une i Sane.
Grad je najprije nastao iz dva podgrada, Podnovi sam Ustisana, pod Kulinskim brdom na kojem je Stajao tvrdi Kaštel akropolskog tipa Knezova Babonjića za nadzor riječnog i cestovnog saobraćaja dolinama Une i Sane koje se upravo sastaju ispod Kulinskog Brda, gdje su prvi začeci Bosanskog Novog.
Srednjovjekovne geografske Mape i Stari dokumenti vrlo često spominju ovu utvrdu u raznim varijantama njegovog imena kao Novi Grad, Novo Kastro, Novigradec, Kastrum, Ujvar itd. Bio je to nevelik, ali u doba Hladnog oružja da teško pristupačan grad, sa jednom donžom, kulom sa četiri sprata, oborom, kapikulama i dva kamena zidana objekta za smeštaj posade.
Njegova podgrada Podnovi bila je smještena na sjevernim padinama Kulskog Brda (Danas Tunjica i Londža), a podgrada Ustisana na današnjoj lokaciji željezničke stanice. To je danas gradska četvrt Prekosanje gdje je vjerovatno bilo riječno pristanište za Unsko-sanske lađare.
Pad srednjovjekovne Bosne pod osmanlijsku vlast primorao je knezove Babonjiće, koji su se zbog utvrđenja Blagaj Grada prozivali blagajski, da stvore savez sa knezovima Zrinskim Kako bi se ujedinili i suzbili invaziju Osmanlijskog carstva. Zahvaljujući toj privremenoj Složi, Ovi bosanski velikaši su uspjeli 1483. godine nanijeti težak poraz osmanlijskoj provalnoj vojsci. Međutim, Sloga domaćih feudalaca bila je kratkog vijeka i samo je privremeno odgađala pad grada. Godine 1519. posljednji put na Kulskom brdu, se pominje podgrada Ustisana.
Više ranije je bio ugrožen Blagaj Grad smješten u dolini Sane, istočno od Bosanskog Novog na Udaljenosti od 7 km. Osmanlije su 1537. godine definitivno zauzeli Blagaj Grad, iz njega protjerali posadu i postavili svoje mustafhize.
Negdje u to vrijeme pao je i Novi na Kulskom brdu, ali su Zrinski još krajem petnaestog vijeka izgradili Novi Novi na lijevoj obali Une da bi se dalje štitili od osmanlijskih prodora. To je usporilo nadiranje Osmanlija na Zapad. Austrijske posade su odoljevale napadima sve do 1556. godine, kada je poslije pada tvrđave Kostajnica osmanlijski Vojskovodja bošnjačkog porijekla, Malkoč-beg osvojio grad Novi Novi 1557. godine.
Osvajanjem Novog Osmanlije su ovo Utvrdjenje pretvorili u važnu vojnu bazu za dalji prodor ka Beču.
Izgrađen je most preko rijeke Une, a grad je veoma brzo naseljen muslimanskim stanovništvom. Grad je ostao pod vlašću Osmanskom sve do 1687. godine, kada ga je zauzela Banska vojska Petra Erdedija.
Muslimansko stanovništvo prebjeglo je preko Une u Bosnu i na prostoru ade Jelenice, danas gradski Kvart Stari Grad, izgradilo tvrđavu od balvana i nasipa na prostoru od hotela „Una“ do gradskog muzeja.
Godine 1726. Počelo je zidanje novog utvrđenja od tesanog, kvalitetnog kamena tako da je po njegovom završetku bio gotovo neosvojiv za ondašnja napadna dejstva i oružja. Prema postojećim skicama Tvrđava Turski Novi imala je zidove visoke 7 m, jarak širok 6 m, a dubok 3 m, bila je dugačka 200 m, 150 m Široka, te imala 5 bastiona (tabije) i dvije kapikule (ulazne kule).
U tvrđavu se ulazilo preko dva mosta, lančanika, a jarkom oko tvrđave tekla je voda iz Une. Osvojena je samo jedanput 1788. godine, poslije mnogih juriša i duge opsade dvadesetostruko jače vojske austrijskog feldmaršala Ernesta Gideona Laudona, zahvaljujući velikoj premoći u ljudstvu i artiljerijskim oruđima. Poslije toga granica se ipak stabilizovala na Uni, tako da su Osmanlije ostale u Novom sve do 1878. godine.
Godine 1878. prema odluci Berlinskog kongresa Novi je zajedno sa ostatkom Bosne i Hercegovine pripao Austro-Ugarskoj.
Okupacione vlasti su 1894. godine do temelja porušile novsku tvrđavu, a njen materijal ugrađen je u razne javne i privatne objekte.
Iduće godine Novi je dobio ime Bosanskog Novog, koje je nosio sve do 1992. godine.
Tokom rata u Bosni i Hercegovini odlukom vlasti Ime Bosanskog Novog je promijenjeno u Novi Grad, zajedno sa ostalim imenima gradova i opština koje su u svom imenu sadržavale pridjev bosanski.
Poslije izmene Zakona o jedinstvenom matičnom broju BiH (član 5. ovog zakona) gradovi koji su za vrijeme ratnih dešavanja u BiH dobili ili imali dvoimeno ime, utvrđen je da dotadašnji dvoimeni naziv Bosanski Novi/Novi Grad ostaje samo Novi Grad.