Pilsēta dibināta 1241. gadā un līdz pat 1945. gadam saucās Bartenšteina (Bartenstein). Pirms Vācu ordeņa ierašanās, apmetne bija prūšu novada Bārtas centrs. Par pašas pilsētas nosaukumu tomēr ir dažādi viedokļi. Bez Bartas novada nosaukuma kā pilsētas vārda sastāvdaļas tiek uzskatīts, ka Bartenšteinas nosaukums radies no seno augšvācu barta (kaujas cirvis)[nepieciešama atsauce], kas attēloti pilsētas ģerbonī, bet cita versija apgalvo, ka pilsētas nosaukums radies no Bartolomeja vārda.[nepieciešama atsauce] 1262. gadā, Lielās prūšu sacelšanās laikā pils tiek nopostīta, tomēr ordenis Balgas komtura vadībā to atjauno. Trīspadsmitgadu kara laikā pilsēta ietilpst Prūsijas konfederācijā, tomēr paliek Prūsijas sastāvā.