Historia thumb|Pasewalk ca. 1615 thumb|Mühlentor (Brama Młyńska) Od początków osady do wojny trzydziestoletniej Legenda głosi, że osadę założyli w VII–VIII wieku dwaj bracia – piraci, którzy znaleźli schronienie w trudno dostępnym miejscu przecięcia Wkry ze starym szlakiem handlowymC. Plötz: Pasewalk 1848-1945 (...), s. 11.. Autor annałów klasztoru Pegau, opisując historię rodziny Wiprechta Starszego, donosi o istnieniu grodu Posduwlc w kraju pomorskim (dokument datowany na 1029 rok). Miejsca położenia grodu do dzisiaj nie udało się ustalić. Obok niego istniała osada słowiańska, wtedy już znacząca i zamożna, w której – jak donosi Wiprecht – można było zdobyć „niesłychanie bodatą zdobycz” (praedam incredibilem). Źródła pisane po raz pierwszy nazywają Pasewalk miastem (civitas) w 1276. Pewne jest jednak, że uzyskał on prawa miejskie już wcześniej, przypuszczalnie na początku lat pięćdziesiątych XIII wieku. Pasewalk od początku swego istnienia należał do Pomorza, jednak z uwagi na pograniczne położenie stanowił przedmiot sporów terytorialnych toczonych przez książąt pomorskich z margrabiami brandenburskimi. Nieraz też zmieniała się jego przynależność terytorialna.