Dlhší čas sa za prvú písomnú zmienku o Novom Meste nad Váhom považovala listina Bela IV. z roku 1253. Pri odbornom skúmaní tejto listiny sa však zistila jej nepravosť, a preto prvou doloženou písomnosťou je listina z roku 1263, v ktorej Bela IV. daroval Nové Mesto nad Váhom benediktínskemu kláštoru sv. Martina na Panónskej hore. Spolu s mestom mnísi dostali obce Streda (Horná Streda), Potvorice a dnes už zaniknuté osady Debrete a Lubov. Počas sporov medzi členmi uhorskej kráľovskej dynastie sa mesto dostalo do rúk sriemskeho bána Vavrinca. Začiatkom 14. storočia sa mesta i Beckovského hradu zmocnil Listina Bela IV. z roku 1263, prvá písomná zmienka Nového Mesta nad Váhom.
Matúš Čák Trenčiansky, ktorý potom ovládal celé Považie až do svojej smrti roku 1321. Prvé kráľovské výsady a práva, napr. 2- x ročne konať jarmok, naše mesto dostalo od kráľa Žigmunda Luxemburského v roku 1388. V tomto istom roku Žigmund Luxemburský daroval Beckovský hrad s mestečkami Beckov a Nové Mesto a ďalších 16 dedín vojvodovi Stiborovi, ktorý bol v tom čase najmocnejším a najbohatším uhorským veľmožom. Stibor si hrad Beckov zvolil za svoje sídlo a nechal ho veľkoryso prestavať.
V roku 1414 Vojvoda Stibor povolal do Nového Mesta rehoľu augustiniánov, ktorí tu založili prepošstvo s kapitulou. Novomestskej prepozitúre daroval dediny Pobedim a Bašovce so všetkými poliami, mlynmi a ďalšími príjmami. Plánoval rozsiahlu gotickú prestavbu novomestského kostola, ktorú však pre náhlu smrť nestačil realizovať. Mal jediného syna a dediča, Stibora, ktorý síce nedosiahol postavenie otca, ale v časoch husitských vojen sa ako kapitán Považia zaslúžil o obranu juhozápadného Slovenska. Na príkaz kráľa dal postaviť mestské hradby, aby Nové Mesto ochránil pred husitmi. Napriek tomu sa však
Gotická socha madony, ktorú Stibor ml. daroval novomestskému kostolu. V čase reformácie bola prevezená do Koryčian (Česká republika – Morava)
Napriek tomu sa však mesto nevyhlo v rokoch 1431 a 1432 husitským útokom. Stibor II. dokončil prestavbu farského kostola začatú jeho otcom vojvodom Stiborom. Po smrti Stibora II. (1434) sa Nové Mesto dostalo prostredníctvom Pavla Bánfiho, manžela dcéry Stibora II., do vlastníctva šľachtického rodu Bánfiovcov.
Živý obchodný ruch prospieval rozvoju mesta, jeho hospodárska sila stále rástla. Prosperitu mesta chceli využiť páni Beckova na zvýšenie svojich príjmov, čo viedlo k neustálym sporom s Novomešťanmi. Ferdinand I. v roku 1550 potvrdil privilegiálnu listinu Žigmunda Luxemburského, do ktorej sa Novomešťanom podarilo vložiť niektoré nové dôležité výsady a práva. Tieto podporili ďalší hospodársky rozvoj mesta. Obyvatelia napr. získali právo vysádzať vinice na okolitých kopaniciach a brať z nich úrodu, boli oslobodení od všetkých prác na kráľovských hradoch, mohli v kráľovských lesoch ťažiť stavebné a palivové drevo a loviť ryby.
Ďalej získali právo voliť richtára a prísažných, právo trestať zbojníkov v určenom okruhu, k čomu si zapožičiavali kata z Trenčína alebo z Trnavy. Veľký hospodársky význam malo právo konať štyri výročné trhy. Bez dovolenia richtára nikto nesmel okrem občanov Nového Mesta predávať na výročnom jarmoku látky. Na týždennom jarmoku boli občania oslobodení od platenia poplatkov a mohli si slobodne stavať na Bzinskom potoku mlyny na mletie obilia a valchy. Novomešťania do listiny dopísali aj právo stavať mlyny a právo meča. Nové Mesto sa ani takýmto spôsobom úplne neoslobodilo od vplyvu Beckovského panstva. Podľa uzavretej dohody s beckovskými pánmi museli Novomešťania platiť panstvu ročnú daň 500 zlatých a museli pracovať v panských viniciach.
Na konci 16. stor. (v r. 1598) malo Nové Mesto 200 domov a stalo sa pomerne hospodársky silným obchodným mestečkom.
