LTIstoriniuose šaltiniuose Naujamiesčio gyvenvietė minima nuo XIV a. antrosios pusės. Senuosiuose dokumentuose randami įrašai apie Novo Miesto dvarą, priklausantį didikams Valavičiams. Po trečiojo Abiejų Tautų Respublikos padalijimo Naujamiestis atiteko Rusijai ir priklausė Radviloms, o nuo XIX a. vidurio Naujamiesčio dvarą ir žemes valdė Karpių giminė. Tuo laiku miestelis dar labiau išaugo, ir visais šiais periodais kalbama apie Vytauto Didžiojo laikais į tą vietovę atkeltus karaimus. Manoma, kad tada gyvenvietė vadinta Karaimų Nauju miestu.