Olsztynek powstał na terytorium pruskiego plemienia Sasinów. Ziemie te, podbite przez zakon krzyżacki, zostały objęte akcją kolonizacyjną dopiero w połowie XIV wieku. Była to kraina puszczańska, pokryta wielkimi lasami, tylko w niektórych miejscach istniały osady pruskie. Tam z reguły Krzyżacy wznosili zamki obronne, a wokół nich powstawały miasta. Najwcześniej lokowano Iławę (1305) i Dąbrówno (1326). W wyniku nasilenia akcji osadniczej założono Ostródę (1348), Działdowo (1349) i dopiero Olsztynek (1359). Ostatnim miastem powstałym na tych terenach była Nidzica (1381). 

Założenie Olsztynka wiąże się z działalnością komtura ostródzkiego, Gunthera von Hohenstein. Z jego inicjatywy na niewielkim wzgórzu zbudowano zamek, obok powstała osada zamieszkała przez rzemieślników i kupców. 1 października 1359 roku otrzymała prawa miejskie i nazwę "Hohenstein" na cześć komtura ostródzkiego, który dokonał lokacji.

Miastu nadano 47 łanów ziemi na prawie chełmińskim, stanowiło to około 1765 ha. Pod zabudowę, przeznaczono tylko niewielką część tej ziemi, większość stanowiła źródło utrzymania dla sołtysa, bogatszych mieszczan i kościoła parafialnego. Zapewne wliczono w to również las miejski i Jezioro Jemiołowskie. Pod zabudowę miejską wyznaczono prostokąt, o powierzchni około 4,16 ha. Obszar ten odpowiada przestrzeni zawartej w obrębie murów miejskich. Olsztynek reprezentował typowe niemieckie miasto na wschodzie, z prostokątnym rynkiem w centrum, przez który przechodziła główna ulica. W rynku znajdował się ratusz. W części północnej, na niewielkim wzniesieniu, stał gotycki zamek, murowany z kamienia i czerwonej cegły, odgrodzony od miasta murami obronnymi. Tuż obok zamku wzniesiono kościół parafialny, również otoczony murami obronnymi aż do XVIII wieku. Zamek i kościół były ważnym punktem obrony w czasach, kiedy fortyfikacja grodu składa się z drewnianej palisady.

Zabudowę miasta stanowiły dwa regularne ciągi różnej wielkości działek, usytuowanych naprzeciw siebie po obu stronach rynku. Domy budowano w sposób zwarty, czyli jeden przy drugim. Na zapleczu każdego z nich mieścił się dziedziniec, zamknięty wjazdem do stajni. Stąd na tyłach działek mieszczańskich znajdowały się tzw. ulice tylne lub stajenne. Teren pomiędzy działkami mieszczańskimi a murem obronnym wypełniono budami, stanowiącymi mieszkania dla biedoty. Na początku XVII wieku. było 59 dużych domów mieszczańskich, małych domów, czyli bud natomiast 77. Można z dużym przybliżeniem wyliczyć, iż w obrębie murów miejskich mieszkało około 700 osób. 

Lata 1359-1410 to dobry okres dla miasta. Rozwijało się rzemiosło, reprezentowane przez piekarzy, rzeźników szewców, krawców, sukienników i garncarzy. Codzienne życie ludności ożywiały i wzbogacały cotygodniowe jarmarki oraz kontakty handlowe z polskim Mazowszem. Patrycjat składał się z rodzin pochodzenia niemieckiego, uboższe warsztaty, czyli tzw. plebs i pospólstwo, wywodziły się natomiast z polskich osadników przybyłych z Mazowsza. Świadczy o tym chociażby spolszczenie nazwy miasta. Już na początku XV wieku pojawia się nazwa "Parvum Olsten'', użyta przez Jana Długosza przy opisie bitwy pod Grunwaldem.

Rok 1410 był początkiem nieszczęść dla ludności Prus Zakonnych. Sprowokowane przez stronę krzyżacką wojny z Polską ciągnęły się przez dziesiątki lat i przyniosły ogromne straty i zniszczenia. Po bitwie grunwaldzkiej miasto i zamek poddały się bez walki wojskom polskim. 17 lipca „z wojskiem swym wyruszył król Władysław Jagiełło], a do zamku i miasta Olsztynka przybywszy, obozem się rozłożył. A gdy w ręce królewskie oddały się zarówno zamek olsztynecki, jak i miasto, Janowi Kretkowskiemu, rycerzowi herbu Dołęga, oddał je król w dzierżawę [...] W piątek rano, 18 lipca, w dzień św. Arnulfa, zwinął król obóz, a przybywszy nad jezioro zwane olsztynkowskim, pomiędzy Morągiem a Olsztynkiem leżące, urządził postój". Tyle Jan Długosz napisał o pobycie Władysława Jagiełły w okolicach Olsztynka. Pewnym jest, iż król polski spędził noc z 17 na 18 lipca niedaleko Olsztynka, w lesie miejskim. Miejsce to, aż do czasów nowożytnych nazywano w gwarze ludowej Jagiełkiem. W źródłach niemieckich nazwa ta figuruje jako „Jagielleck". Przez długi czas miejscowa ludność pokazywała rozłożysty dąb, pod którym odpoczywał polski monarcha. W czasie powrotu spod Malborka wojska polskie wyrządziły w Olsztynku znaczne szkody szacowane na ogromną sumę 14700 grzywien; 30 mieszkańców straciło życie. Straty poniosły również okoliczne wioski i majątki.
W 1414 roku w okresie tzw. wojny głodowej wojska polsko-litewskie wtargnęły do Prus. Zakon polecił spalić Olsztynek, nie mogąc go bronić. Ludność uciekła z dobytkiem w okoliczne lasy. Na szczęście miasta nie spalono, chociaż dostało się ono krótki czas w ręce wojsk polsko-litewskich. Tym razem straty oszacowano na 7000 grzywien. Zniszczeniom uległy ratusz, kościół, zamek (częściowo spalony) i dwa młyny. Zabito 67 mieszkańców Olsztynka. Prawdopodobnie po tych wydarzeniach rozpoczęto wznoszenie murów obronnych oraz odbudowano zniszczone młyny.

W okresie wojny trzydziestoletniej (1454 - 1466) Związek Pruski został poparty przez Olsztynek, w kilka miesięcy później zdobyły go wojska krzyżackie. Ważność Olsztynka polegała na tym, iż był najdalej wysuniętym na wschód punktem oporu Krzyżaków. Przez dłuższy czas stały tu czeskie wojska zaciężne pod dowództwem Mužika ze Świniawy. Dały się one bardzo mocno we znaki mieszczanom, rygorystycznie egzekwując ogromne podatki. W wyniku podpisania pokoju toruńskiego w 1466 roku Olsztynek pozostał w granicach państwa krzyżackiego, podczas gdy Warmia oddalona zaledwie o 5 km na północ została włączona do Polski. Wojna trzydziestoletnia mocno zrujnowała całe Prusy. Olsztynek był również w znacznym stopniu zniszczony i splądrowany. Mieszczanie, nauczeni przykrym doświadczeniem, wzmocnili mury obronne i zbudowali bramy z solidnymi wieżami.

Podczas ostatniej wojny polsko-krzyżackiej (1519 - 1521) wojska polskie zajęły Olsztynek w 1520 roku. Hetman polski, Mikołaj Firlej, wstawił mieszkańcom pisemne zapewnienie, że król Zygmunt zachowa wszystkie przywileje miasta. Pozostała tu stuosobowa załoga polska, która okupowała Olsztynek aż do układu krakowskiego w 1525 roku.

Wydarzenia 1525 roku miały ogromne znaczenie dla dalszych dziejów ziem pru­skich. W tym czasie ówczesny mistrz zakonu krzyżackiego, Albrecht Hohenzollern, pod wpływem nauk Marcina Lutra postanowił rozwiązać zakon krzyżacki, zrezy­gnować ze ślubów zakonnych i utworzyć państwo świeckie. Szczególny wpływ na tę decyzję oraz na sprawy reformacji w Prusach miały rozmowy Lutra z wielkim mistrzem prowadzone w Wittenberdze 29 listopada 1523 roku. Tak powstały Prusy Książęce ze stolicą w Królewcu. Państwo to, zgodnie z traktatem krakowskim, by­ło lennem Polski i dlatego jego władca musiał złożyć królowi polskiemu hołd. Al­brecht był zwolennikiem reformacji i Prusy Książęce stały się pierwszym państwem luterańskim na świecie. Zgodnie z zasadą „czyj kraj, tego religia" ludność tego państwa przeszła na luteranizm. Odbyło się to drogą pokojową. Ogromna większość społeczeństwa poparła dążenia księcia i głosicieli nauk Marcina Lutra. Zorganizowanie Kościoła ewangelickiego w Prusach Książęcych wymagało znalezienia przede wszystkim odpowiedniej liczby pastorów i wydrukowania nowych książek religijnych. Wielu duchownych rekrutowało się z dawnych księży katolickich, którzy opowiedzieli się za nową nauką, wielu też pastorów przybyło z ziem polskich. Było to ważne, gdyż znali oni język polski, a w tym czasie w Prusach Książęcych mieszkało około 100 000 osób mówiących wyłącznie po polsku.
W czasach poreformacyjnych Olsztynek stał się ważnym centrum kościelnym. Pierwszym ewangelickim duchownym był Matthias Bienwald, przybyły tu ze Śląska; 20 czerwca 1526 roku książę Albrecht mianował go pierwszym proboszczem w Olsztynku. Ewangelicy przejęli dawny kościół katolicki. Bienwald prowadził korespondencję z ewangelickimi reformatorami: Speratusem i Polentzem. W 1554 roku został wyróżniony i powołany do prowadzenia Synodu w Saalfeld, który miał zakończyć spory wynikłe między ewangelickimi duchownymi na terenie Księstwa.

Wydarzenia roku 1525 spowodowały podziały religijne na terenie dawnych Prus. Ludność Warmii, należącej do Polski od 1466 roku, pozostała wierna Kościołowi katolickiemu, a mieszkańcy Prus Książęcych, w tym osadnicy polscy z Mazowsza, zostali ewangelikami. Tych polskich ewangelików w późniejszych czasach zaczęto nazywać Mazurami.

Od 1525 roku przez prawie sto lat trwał korzystny czas dla ziem i ludności Prus Książęcych. Wojny omijały te tereny, a ożywione kontakty z Polską sprzyjały rozwojowi gospodarczemu. W tym okresie Olsztynek nabrał dużego znaczenia.

W 1525 roku utworzono starostwo, które przetrwało do 1610, kiedy to ziemię olsztynecką włączono do starostwa ostródzkiego. Główną powinnością starosty był nadzór nad sprawami wojskowymi, czyli organizacja obrony i budownictwa obron­nego, utrzymywanie wojska oraz ściąganie kontrybucji na jego potrzeby. O tym, jak znacząca rolę odgrywał starosta w XVI wieku, świadczy fakt, że w 1546 roku przy­był do miasta książę pruski, Albrecht Hohenzollern, z małżonką, by uczestniczyć w weselu starosty Dietricha von Wernsdorf. Prócz starosty rezydowało jeszcze paru urzędników państwowych: pisarz urzędowy, burgrabia, nadleśniczy, nadzorca ry­bactwa, komornik.

Olsztynek stal się też ważnym centrum kościelnym. Utworzono tutaj archiprezbiterat (odpowiednik biskupstwa), istniejący cło 1699 roku. W 1534 założono szkołę partykularną, której absolwenci mieli prawo do studiów uniwersyteckich. W metry­ce Uniwersytetu Królewieckiego w latach 1544 - 1688 zapisano 73 studentów z Olsztynka, co stanowiło bardzo wysoka liczbę w porównaniu z liczbą studentów z innych miast, na przykład z Ostródy.

W połowie XVI wieku dokonano remontu kościoła, murów obronnych i bram. Ist­niał już wtedy szpital, a właściwie przytułek dla ubogich, utrzymywany z ofiar i da­rowizn. Miasto posiadało taż swój wilkierz, czyli zbiór przepisów regulujących życie wewnętrzne. Wilkierz ten odczytywano wszystkim mieszkańcom każdego roku w środę po Zesłaniu Ducha Świętego. Władzę sprawowała rada złożona z kilku raj­ców z burmistrzem na czele. W jej rękach spoczywała także część władzy sądowniczej. Około 1600 roku burmistrzem Olsztynka został Friedrich am Ende. Mający dużą władzę i nie mniej dochodów. Jego prawą ręką był pisarz miejski, który rów­nież posiadał dobre zabezpieczenie materialne.

Mieszkańcy Olsztynka utrzymywali się z rzemiosła i handlu, dodatkowe źródło dochodów stanowiły rolnictwo i ogrodnictwo. Rzemieślnicy, zorganizowani w cechach, mieszkali zazwyczaj w jednej części miasta, razem siadali w kościele i mieli wyznaczony dla siebie odcinek murów miejskich do obrony. Olsztynek posiadał kilka młynów, stanowiących własność panującego, oraz miejskie browary, w których obywa­tele miasta mieli prawo warzyć piwo na własny użytek lub na handel.
W latach 1491-1715 działał też sąd ziemski, rozpatrujący sprawy nie tylko ludzi wyż­szego stanu, ale i niższego, na przykład sprawy kradzieży drzewa z lasu, przekroczenia prawa miejskiego. Do wykonywania wyroków trzeba było wynajmować kata z większe­go sąsiedniego miasta, a szubienica stalą poza obrębem murów, na polu Grislinga.

Wiek XVII przyniósł Prusom Książęcym oraz ziemiom Rzeczypospolitej wiele nie­szczęść w postaci wojen, pożarów, głodu i epidemii. Wszystkie te kataklizmy spowodowały ogromne zniszczenia, straty w ludności i upadek gospodarczy. Szczególnie tragiczne w skutkach okazały się tzw. wojny szwedzkie, które zaczęły się w 1626 roku i trwały z przerwami do 1660 roku.

W 1651 roku doszło do pożaru, który poważnie zniszczył miasto. Kolejne nieszczęście, w 1655 roku, spowodowane było nadejściem wojsk szwedzkich. Wielu męż­czyzn opuściło swoje żony i dzieci, aby pójść na wojnę. Miasto uległo spustoszeniu, a kontrybucje, kwaterunki i podwyższone podatki doprowadziły mieszkańców do wielkiego zubożenia. Gdy władca Prus Książęcych, elektor Fryderyk Wilhelm III, zdradził Polskę przechodząc na stronę Szwedów, wojska polsko-tatarskie rozbiły w bitwie pod Prostkami 8 października 1656 roku wojska brandenbursko-szwedzkie. Prusy Książęce stanęły otworem, wówczas to Tatarzy dokonali spustoszenia ziem pruskich. Powtórny najazd Tatarów nastąpił zimą 1657 roku. W sumie spalili 13 miast, 249 wsi, 37 kościołów, uprowadzili w jasyr 34 000 ludzi, zabili kilka tysię­cy. Następstwem tych barbarzyńskich najazdów była epidemia dżumy, która zdziesiątkowała ludność Prus Książęcych, głównie Mazurów. W Olsztynku zmarło 300 osób na 800 mieszkańców; liczbę wszystkich ofiar na Mazurach szacuje się na bli­sko 85 000. 30 października 1685 roku wybuchł straszliwy pożar, który obrócił w ruinę niemal całe miasto. Spaliły się kościół, plebania, ratusz i prawie wszystkie domy mieszczańskie. Klęska była tak wielka, że elektor zwolnił na dziesięć lat Olsz­tynek od wszelkich podatków oraz zarządził w całym Księstwie zbiórkę pieniędzy na odbudowę.

Przeprowadzona w 1695 roku wizytacja parafii w Olsztynku wykazała ogromne zu­bożenie ludności. Wizytatorzy narzekali, że szczególnie w wioskach jest zbyt dużo prostytutek, które nie płacą należnych kar do kasy kościelnej. Członkom parafii za­kazano pochówku zmarłych bez dokonania odpowiednich opłat. Wszystkie wioski od dłuższego czasu zalegały z dziesięciną, również z młynów dochód był bardzo mały, ponieważ wielu młynarzy odeszło lub zmarło w czasie zarazy.

Domy miejskie po pożarze z 1685 roku w dużej mierze odbudowano, przypominały one jednak bardziej wiejskie chałupy niż domy patrycjuszy. Stały szczytami do rynku lub ulicy, kryte były strzechą lub trzciną. Składały się z korytarza, małej izby, jednej ciemnej komory i większego pokoju. Za domami znajdowały się ogródki, podwórza oraz stodoły budowane rzędami, tworząc charakterystyczne ulice stodół.

W 1708 wybuchła epidemia dżumy, którą zaraził mieszkańców Olsztynka syn kapelusznika, powróciwszy z Polski. Zmarła cała rodzina nieszczęsnego kapelusznika oraz znajomi odwiedzający chorych. Ludzie w panice uciekali do pobliskich lasów i wiosek, wkrótce jednak wojsko pruskie otoczyło ścisłym kordonem całe miasto, aby nikt nie mógł się wydostać. Blokada była bowiem jedynym sposobem umożliwiającym powstrzymanie rozszerzania się zarazy. W Olsztynku działy się dantejskie sceny, ludzie chorowali i umierali w strasznych cierpieniach. Brakowało też żywności i szerzył się głód. W ciągu trzech tygodni zmarło 90 osób. Nad miastem zawisło widmo całkowitej zagłady. Dopiero na przełomie roku 1708 na 1709 silne mrozy zahamo­wały postęp epidemii. Zima ta była długa oraz bezśnieżna, ale za to wyjątkowo mroźna. Potem przyszło późne, ale upalne lato. Klęska nieurodzaju spowodowała głód, a wraz z nim doszło do nawrotu jeszcze straszniejszej zarazy, która spowodowała ogromną śmiertelność. Z domostw, gdzie wymarły całe rodziny, rabowano sprzęt, żywność i odzienie nie bacząc, że w ten sposób przenosi się zarazę i sobie gotuje śmierć. Epidemia "czarnej śmierci" szalała jeszcze w 1710 roku i za­częła wygasać w 1711. Jej skutki były straszliwe: w Olsztynku wymarła połowa mieszkańców, niektóre wioski i miasta uległy całkowitemu wyludnieniu. Spośród 600 000 osób w Prusach zaraza pochłonęła około 200 000 ofiar. Najbardziej ucierpiały najbiedniejsze rejony mazurskie; 10 000 zagród chłopskich stało opuszczo­nych, wymarły bowiem całe rodziny.

W okresie wojny siedmioletniej (1756 - 1763) Prusy znalazły się pod okupacją Rosji, której wojska zajmowały ziemie pruskie w latach 1758 - 1762. Wycofały się do­piero po śmierci carycy Elżbiety II.
Kolejny wielki pożar z 16 kwietnia 1804 roku strawił niemal cale miasto; spaliły się ratusz, pastorówka, Brama Niemiecka, 108 domów, 73 stajnie, 3 spichlerze, 37 stodół i 37 szop. Przyczyną tej tragedii było prawdopodobnie zaprószenie ognia w jed­nej z szop.