Okolie mesta bolo osídlené už v najstarších dobách. Archeologický výskumami v severovýchodnej časti mesta v oblasti Mnešíc sa zistilo, že sprašový profil obsahuje až 5 kultúrnych vrstiev. Nálezy zo spodnej vrstvy pochádzajú z obdobia 240 000 rokov pred naším letopočtom, čím sa mesto radí medzi najvýznamnejšie paleolitické lokality. Osídlenie v neskorších dobách potvrdzujú neolitické nálezy z okolitých obcí a lužické popolnicové pole v Novom Meste nad Váhom.

     Vznik stredovekej osady súvisí s budovaním pásma pohraničných  pevností na hrebeňoch Malých a Bielych Karpát, ktoré chránili západné hranice Uhorska. Sústavu hradov  dopĺňali strážne veže a opevnené osady, ako bola i osada, z ktorej sa vyvinulo Nové Mesto nad Váhom. Jej vývoj podporovala výhodná poloha na považskej ceste s odbočkami a Moravu a cez Vážsky brod na Beckov. Za tatárskeho vpádu bola pôvodná osada zničená. Jej presná poloha nie je známa. Obyvateľstvo, ktoré vpád prežilo, usadilo sa potom na prirodzene chránenej terase, dvíhajúcej sa asi 1-1,5 km od pravého brehu Váhu a klesajúcej smerom na západ, odkiaľ ju obtekala riečka. Vybudovanie osady na novom mieste dalo podnet ku vzniku jej nového pomenovania - Nové Miesto. Názov mesta v stredovekých listinách sa uvádza vo viacerých podobách: Villa regia, Nova cvitas, Nova villa possesio regalis de Ujhel, Nova villa iuxta Vag, Vyhel, Ujhely, Vagujhely, Wag Neustadt, dnešný názov poznáme od roku 1584.

     Najstarší písomný doklad k dejinám Nového Mesta je listina z 23.5.1253, v ktorej ho kráľ Béla IV. povyšuje na mesto za služby, ktoré mu preukázali jeho obyvatelia v dobe tatárskeho vpádu. Ďalšia písomná správa je z r. 1263, kedy ho Béla IV. Dal kláštoru sv. Martina na Panónskej hore spolu s trhovými a prievoznými poplatkami. Benediktíni dostali Nové Mesto i s dedinami Debrete, Lubo Streda a Potvorice, ktoré patrili k Novému Mestu nad Váhom. Dediny Lubo a Debrete neskôr zanikli a ich poloha nie je známa. Nové Mesto nad Váhom dostali benediktíni ako náhradu za hrad Gössling za 800 mariek striebra, ktoré si kráľ požičal od kláštora po prehratej bitke. Obyvatelia ako poddaní kláštora mali značnú samosprávu. v menších veciach ich súdili vlastní richtári, vo vážnejších veciach sám kráľ, župan a sudca ich nemali právo súdiť.

    Za dynastických sporov kráľoviča Štefana s otcom sa benediktíni postavili na stranu otcovu, za čo sa im Štefan V. po nastúpení na trón pomstil. V roku 1271 im Nové Mesto odobral a daroval ho sriemskému bánovi - komesovi Vavrincovi. Bánov vnuk Ladislav IV. potvrdil r. 1273 donáciu v prospech benediktínov, ale už o rok ju vyhlásil za neplatnú a Nové Mesto s majetkami prinavrátil Vavrincovi. Benediktíni sa snažili dostať svoje majetky späť, ale bezvýsledne, pretože Matúš Čák Trenčiansky zabral nielen Nové Mesto ale i celé Považie. V roku 1388 dostal beckovský hrad od kráľa  Žigmunda poľský vojvoda Ctibor, ktorý sa stal pánom i Nového Mesta. 

      V 14. storočí sa mesto sformovalo v stredoveké opidum. Ďalšie osudy mesta sú spojené s osudmi beckového hradu, keďže sa stalo trvalou súčasťou panstva. Ctibor zriadil v roku 1414 v meste Augustiansku prepozitúru, prestavil v sluhu gotickom staršiu románsku baziliku a jeho syn Ctibor II. opevnil mesto hradbami. Opevnenia však neodolali husitským výpravám na Považí. V roku 1428 husiti spustošili kraj od Bratislavy až po Nové Mesto nad Váhom a vrátili sa do Uherského Brodu, kde zanechali trvalú posádku. Ctibor z obavy pre novými výpravami dal r. 1430 znovu opevniť. Hradby boli z menej trvanlivého materiálu, preto boli pre husitov slabou prekážkou a v roku 1431 a 1432 mesto znova dobyli. Po smrti Ctibora II. sa mesto dostalo v roku 1434  do vlastnícatva Pavla Bánfyho, nového majiteľa Beckovského hradu. 

     Mesto sa postupne stáva dôležitým obchodným strediskom na západnom Slovensku. Na výročných jarmokoch a týždenných trhoch sa vymieňal rôzny tovar, mesto vyvážalo na Moravu vínu, bolo vážskym prístavom pre plte, ktoré sa plavili dolu Váhom až po Dunaj. V roku 1550 Ferdinand I. dal mestu výsadnú listinu a ňou zbavil obyvateľov mesta závislosti   na Beckovskom hrade. Obyvatelia už nemuseli pracovať na kráľovských hradoch, mohli vysádzať vinice a obrábať kopanice bez daní. Mesto držalo okrem ďalších výsad i právo meča právo konať jarmoky, na ktorých jeho obyvatelia boli oslobodení od trhových poplatkov. 

     Rozvoj mesta spomalili nájazdy Turkov, ktorí spustošili mesto po prvý raz v roku 1599 a zajali veľa obyvateľov. V roku 1605 vtrhli do mesta hajdúsi Štefana Bocskayho, ktorí zajali veľa občanov. V auguste toho istého roku obsadili mesto českí rytieri, potom vojsko Ferdinanda II. Roku 1624 zahubilo vojsko v meste okolo 500 ľudí. Počas povstania Fraňa Rákoczyho obsadilo mesto cisárske vojsko generála Schlika, ktorý dal podpáliť Kochanovského dom, od ktorého požiar sa rozšíril a zničil takmer celé mesto. Po bitke na bielej Hore v roku 1620 sa do mesta prisťahovalo mnoho majstrov z Čiech a Moravy, ktorí posilnili existujúce remeslá. Z cechov boli najdôležitejšie súkennícky, čižmársky, kožušnícky a hrnčiarsky.

     30.3.1668 sa tu konalo zasadnutie zastupiteľstva Nitrianskej župy, na ktorom potvrdili zemiansku listinu Martina Petroviča, ktorého pravnukom je maďarský básnik Šándor Petöfi. 6.6.1622 bola v meste uložená uhorská kráľovská koruna s ostatnými korunovacími klenotami, ktoré z Trenčína prevážalo do Šoprone 2000 vojakov. V decembri r. 1805 po bitke pri Slavkove hostilo mesto ruského cára Alexandra I.

     Vznik priemyselných podnikov v 19. storočí bol zameraný na spracovanie poľnohospodárskych produktor a na výrobu výrobkov pre poľnohospodárov: J. Kraus výrobňu rumu a likérov, A. Friedler továreň na myslo. Mali tu pálenice aj J. Lövinger, G. Herzog, a E. Taus. H. Tauber založil továreň na podkovz a iné výrobky zo železa. Podobný sortiment mala aj továreň Reisa, kde sa vyrábali najmä vidli, reťaze, klince. Výhodná územná poloha mesta vytvárala vhodné podmienky na pestovanie obilnín, cukrovej repy, krmovín, pôdu vlastnili rodiny veľkostatkárov, ako boli: Hezegovci, Wachtlovci, Kühnovci, Tausovci, Schlezingerovci, Lányovci, Kľúčovskovci,  Stánkovci, Várnovci     .