Lenkijos karaliaus ir LDK didžiojo kunigaikščio Vladislovo IV žmona Cecilija Renata Jurbarko valsčiuje įsikūrusį Duliebaičių kaimą 1643 m. pavertė miestu ir pagerbdama savo vyrą, pavadino jį Vladislavovu. Naujasis pavadinimas žmonėse neprigijo ir vietovė vis buvo vadinama Naumiesčiu arba tiesiog Miestu. Naujai kuriamame mieste 1644 m. karalienės rūpesčiu pastatoma koplyčia ir prie jos pakviečiami įsikurti basieji karmelitai. Jiems išlaikyti iš Jurbarko seniūnijos pajamų paskirta 400 auksinų. Kiek vėliau, 1667 m. karalius Jonas Kazimieras vietoje tų pinigų užrašė vienuoliams 12 valakų žemės Meištuose, dešinėje Šešupės pusėje. Vyskupas Jurgis Tiškevičius karmelitams pavedė valdyti Vladislavovo (arba Naumiesčio) parapiją. Pradžioje ji buvo nedidelė, bet XVII a. pabaigoje jai priklausė virš 100 kaimų. Parapijai plečiantis, Naumiesčio karmelitai 1744 m. įkuria savo filiją Griškabūdyje.

XVII a. II-oje pusėje (1680 m.) karmelitai vietoje jiems funduotos koplyčios pasistatė naują medinę kryžiaus plano bažnytėlę. 1699 m. ją konsekravo Žemaičių vyskupas Jeronimas Krišpinas Kiršenšteinas, savo vizitacijos metu nurodęs, kad Vladislavovo vienuolyne gyvena keturi broliai karmelitai, kurie gavę savo generolo leidimą, prie bažnyčios įsteigė Škaplieriaus Švč. M. Marijos broliją. Praėjus šimtmečiui ir minėtai medinei bažnyčiai pasenus, 1783 m. vienuoliai parapijiečių padedami Naumiestyje pradėjo statyti didelį mūrinį sakralinį statinį ir 1787 m. gegužės 13 d., nors ir ne iki galo užbaigtą, konsekravo Šv. Kryžiaus Atradimo vardu. Žinoma, kad tada nebuvo baigti mūryti bokštai pagrindiniame fasade. Jie iškilo tik XIX a. II-oje pusėje. Yra teigiama, kad naujojo statinio architektu buvęs karmelitas Juozapas Vališauskas, apie kurį įdomiai pasakoja Jonas Totoraitis knygoje „Sūduvos Suvalkijos istorija”:„... ėjęs mokslus Vilniuje, paskui Paryžiuje. Mokslus baigęs, dalyvavęs viename kare. Dėl pralošto mūšio ar dėl kitokios priežasties, gelbėdamasis, kad nepakliūtų į nelaisvę, bėgęs nuo priešų, ir plaukęs per upę. Beplaukdamas pailsęs, ir ėmęs skęsti. Ėmęs šauktis prie Dievo, kad stiprintų jėgas išplaukti ir padaręs apžadą, kad jei išsigelbėsiąs nuo mirties, įstosiąs į Karmelitų vienuolyną. Išplaukęs sveikas, įstojęs į Karmelitus ir pastatęs Naumiesčio mūrinę ir Griškabūdžio medinę bažnyčią”.

Mūrinė Naumiesčio bažnyčia buvo suprojektuota ir pastatyta stačiakampė trinavė bazilika su pusapskrite apside. Bažnyčios išorė monumentali, sunkių proporcijų, santūrių vėlyvojo baroko formų, kuriose jaučiamas ir klasicizmo poveikis. Interjero architektūrą turtina cilindriniai ir kryžminiai skliautai. Ypatingai įdomi skliautinių arkų kompozicija virš vienuolių choro patalpos: į skliautą virš didžiojo altoriaus trikampiu įsijungia apsidės arkos. Vienuolių chorą puošia išlikusios medinės stalės ir dekoratyvi XVIII a. pabaigos vietos meistrų krikštykla.

Tenka apgailestauti, kad, 1803 metais kilęs didelis gaisras mieste, neaplenkė ir karmelitų bažnyčios bei vienuolyno. Ugnis visiškai sunaikino vienuolių gyvenamąjį namą ir bažnyčios šoninių navų stogus. Naumiesčio karmelitai nebeįstengė pataisyti savo bažnyčios, nes nuo 1794 m. priklausydami Prūsijos karalystei, neteko viso savo turto. Gaudami menką kompensaciją, vienuoliai negalėjo tinkamai prižiūrėti didingų statinių. 1805 metais Naumiesčio basųjų karmelitų vienuolynas buvo visai panaikintas. Iš karto po to surašytas inventorius (1806 m.) nurodo prie vienuolyno buvus špitolę, tris daržus ir vieną kluoną. Be to, nuo 1781 iki 1795 metų Naumiestyje, karmelitų vienuolyne veikė pradinė mokykla, kuri buvo pirmoji edukacinė įstaiga mieste. Vienuolių pradėtą švietėjišką veiklą pratęsė 1802 m. įsteigta parapinė mokykla, kuri 1814 m. tapo valstybine ir XIX a. viduryje pertvarkyta į dviklasę miesto mokyklą. Joje mokytis pradėjo nemaža vėliau pasižymėjusių žmonių (Jonas Jablonskis, Pranas Mašiotas, Juozapas Rūgys ir daugelis kitų).

Panaikinus konventą, jo vyresnysis pavarde Birmonas tapo pirmuoju Naumiesčio (Vladislavovo) klebonu ir 1807 m. sudegusio vienuolyno vietoje pastatė mūrinę kleboniją. Šis veiklus kunigas mirė 1829 m., būdamas Seinų katedros kanauninku.

Vienuolių karmelitų veikla, trukusi Naumiestyje 160 metų, neišnyko be pėdsakų. Išliko didinga bažnyčia ir ją puošiantys altoriai, jų paveikslai. Vienas įspūdingiausių — paveikslas „Škaplieriaus Švč. Mergelė Marija”. Jis nutapytas XVIII a. pabaigoje ir vaizduoja soste sėdinčią Mariją su Kūdikiu. Abu jie tiesia škaplierius basųjų karmelitų vienuolijų steigėjams šv. Kryžiaus Jonui ir šv. Teresei Avilietei. Tenka apgailestauti, kad 1970 m. nevykusi restauracija apgadino paveikslą. Nepaisant to, ši tapyta iškilminga kompozicija primena mums čia apaštalavusius karmelitus ir jų pamaldumą į Mariją Škaplierinę Karmelio Kalno Karalienę.