The settlement was first mentioned in 1561 as a village called Duoliebaičiai. In 1639 the town was renamed Vladislavovas (Polish: Władysławów) by Cecilia Renata of Austria after her husband Władysław IV Vasa. He granted the town Magdeburg rights in 1643. However, the name did not achieve popular usage, and the settlement became known as "a town" or "a new town" instead. The German name Neustadt Schirwindt is derived from the former town of Schirwindt, today a small military village called Kutuzovo, which lay just across the border. In 1900 the town began being referred to as Naumiestis (New Town). In 1934 the town was renamed Kudirkos Naumiestis in honor of the Lithuanian patriot, Vincas Kudirka, who lived there from 1895 to 1899. A well-organized Jewish community also lived in there and produced a number of prominent rabbis and Jewish scholars. Its name in Yiddish was נײַשטאָט־שאַקי (Nayshtot-Shaki). Before World War II the town had about 3,000 Jewish residents. Journalist and writerHerman Bernstein was born here in 1876 and Rabbi Abba Hillel Silver was born here in 1893.
In 1941, an Einsatzgruppen of Germans and Lithuanian nationalists murdered the local Jewish population in mass executions, Hundreds of people were massacred.