W XIII i XIV wieku wyludniony obszar Wielkiej Puszczy rozciągał się w całych południowych Prusach i na pograniczu prusko-mazowieckim i prusko-litewskim. Po podboju przez Zakon Prus Górnych i Warmii w XIV wieku stopniowo był kolonizowany od zachodu i północy. Na mocy pokoju mełneńskiego z 1422 roku wytyczono granice między Państwem zakonnym, Polską a Litwą, co dało początek zorganizowanemu osadnictwu.
W XV wieku nieskolonizowany obszar Wielkiej Puszczy obejmował komturie (później starostwa w Prusach Książęcych od 1525 r.): piskie, ełckie, straduńskie, zelkowskie i węgoborskie (węgorzewskie).
Pierwsza faza kolonizacja Wielkiej Puszczy w XV i XVI w. odbywała na południu z dużym udziałem ludności polskiej z Mazowsza (Mazurzy), stąd z czasem obszar ten został nazwany „Pruskim Mazowszem” lub „Pruskimi Mazurami”, a potem skrótowo Mazurami. Jej wschodnią i północną część natomiast zasiedlali również osadnicy litewscy i żmudzcy (Litwini pruscy), stąd znana jest jako Pruska Litwa (lub Mała Litwa).