Przesmyk pomiędzy Tałtami i Mikołajskim była zasiedlana jeszcze w czasach przedchrześcijańskich, o czym świadczy odkrycie znacznych rozmiarów osady w Stawku, znaleziska archeologiczne w Łuknajnie oraz w obrębie rynku w Mikołajkach. Podówczas oba jeziora łączył jedynie wąski strumyk. Mikołajki zostały założone na terenie średniowiecznego Państwa Zakonu Krzyżackiego. Pierwsza wzmianka źródłowa mówiąca o osadzie w miejscu dzisiejszych Mikołajek pochodzi z 1444 r. Wtedy to wielki mistrz Konrad von Erlichshausen nadał niejakiemu Wawrzyńcowi Prusowi 15 włók ( 1 włóka ≈ 18 hektarów) na prawie magdeburskim wraz z pełnym sądownictwem. Osada ta liczyła kilkanaście zagród, na wzgórzu nad nimi wznosiła się Kaplica Św. Mikołaja. Maleńka osada, początkowo nazywana Święty Mikołaj, zaczęła się rozwijać wraz z napływem polskiej ludności z Mazowsza. Już w 1516 r. Jan Nogaj prowadzi za zgodą komtura w Rynie karczmę w Mikołajkach. Podówczas w miejscu dzisiejszej kładki dla pieszych powstał też pierwszy drewniany most zwodzony, na środku była zamontowana podnoszona klapa.
W 1525 r. wielki mistrz Albrecht Hohenzollern rozwiązał Zakon Krzyżacki, przechodząc jednocześnie na luteranizm. Zmieniła się też nazwa państwa na Prusy Książęce, Mikołajki zostały także objęte reformą wyznaniową. Tereny te zostały wyjęte spod jurysdykcji biskupa warmińskiego, w latach 1525-1530 prowadzono ogólnokrajową akcję wprowadzania nowego wyznania. Mikołajską kaplicę przemianowano na luterańską, wkrótce rozbudowując ją do rozmiarów kościoła. Osada się rozbudowywała, w 1555 r. liczyła już 72 włóki, zamieszkałe niemal wyłącznie przez ludność polską. Rozwój Mikołajek zahamowała nieco wojna polsko-szwedzka, w której książę pruski opowiedział się po stronie Szwedów, ściągając tym samym na Prusy Książęce najazd polsko-litewsko-tatarskich oddziałów, który dla Mikołajek przyniósł zniszczenie kościoła. Do tego dołożyła się klęska dżumy w latach 1710-1712, poprzedzona dodatkowo nieurodzajem i plagą myszy. Podupadłe Mikołajki ratowano rozległymi nadaniami ziemskimi oraz podniesieniem osady do rangi miasta. Stało się to 9 grudnia 1726 r., prawa miejskie nadał król Prus Fryderyk Wilhelm I, pierwszy burmistrz Mikołajek nosił przydomek Kopeć. Niełatwą odbudowę miasteczka przerwał pożar z 1729 r. W 1758 r. podczas wojny siedmioletniej Mikołajki zajęły wojska rosyjskie, nie wyrządzając, żadnych większych szkód, podobnie łagodnie przeminął w Mikołajkach okres wojen napoleońskich 1807-1812. Po odejściu wojsk rosyjskich Mikołajki zaczęły korzystać z ruchu handlowego z Giżyckiem za pomocą systemu kanałów pomiędzy Tałtami i Niegocinem. Niestety klęski ognia, zarazy i nieurodzaju dotknęły miasto w latach 30. i 40. XIX w. W 1832 r., w Mikołajkach odbył się spis ludności, wykazujący 178 domów i 1948 mieszkańców, a w 1864 r. odnotowano już 2276 osób, w tym 42 Żydów. Początki turystyki wodnej w Mikołajkach sięgają 1843 r. Pierwszym statkiem był parowiec „Masovia”, który regularnie pływał z Piszu przez Mikołajki do Rynu. Rok 1854 przyniósł wizytę króla Fryderyka Wilhelma IV, wizytującego szlak Wielkich Jezior Mazurskich właśnie z pokładu „Masovii”. Wiek XIX to powolne, acz skuteczne zniemczanie się Mikołajek, podobnie jak i reszty Mazur. Życie w miasteczku nadal kręciło się wokół portu, mieszkańcy poza rybołówstwem zajmowali się handlem rzemieślnictwem oraz rolnictwem. Z tamtego okresu pochodzą także najstarsze zachowane zabytki architektoniczne miasta. Mikołajki długo leżały z dala od głównych ciągów komunikacji lądowej. Dopiero w 1911 r. doprowadzono linię kolejową z Olsztyna do Ełku, przerzucając pierwszy nowoczesny most ponad jeziorami. Niemal jednocześnie wzniesiono również most drogowy, usytuowany pomiędzy dawną kładką a mostem kolejowym.
Mikołajki poniosły znaczne straty podczas I wojny światowej. Już w sierpniu 1914 r. wycofujące się z miasta wojska niemieckie wysadziły przeprawy przez przesmyk pomiędzy jeziorami, zarówno kolejową i drogową. Powybuchowa fala uderzeniowa powybijała szyby w mikołajskich domach oraz kościele. W listopadzie 1914 r. Mikołajki znalazły się na bezpośredniej linii frontu pomiędzy wojskami niemieckimi a rosyjskimi. Po wyparciu Rosjan w końcu 1914 r. wojna odsunęła się od Mikołajek i już do nich nie powróciła. Okaleczone miasteczko objęte zostało ogólno niemiecką akcją pomocy Prusom Wschodnim, patronat nad Mikołajkami objęło pomorskie Choszczno, przekazując miastu 90 tys. marek na odbudowę. Za te pieniądze naprawiono szkody oraz uruchomiono młyn, tartak i fabrykę kamienia. Po modernizacji przystani żeglugi zawijały do niej statki wożące turystów na trasie Pisz – Mikołajki – Giżycko – Węgorzewo. W okresie międzywojennym Mikołajki stały się prawdziwie miastem turystycznym, do którego przybywali także polscy turyści, jak Jędrzej Giertych, Mieczysław Orłowicz i Melchior Wańkowicz. W 1939 r. Mikołajki liczyły 2637 mieszkańców. II wojna światowa działaniami frontowymi wkroczyła na Mazury dopiero na przełomie 1944/1945 r., jednakże Mikołajki już wcześniej wpisały się w historię tej wojny. Od 1940 r. działała w nich placówka służb wywiadowczych Abwehry – Walli II, powiązana z systemem Kwatery Głównej Hitlera w Gierłoży. Tuż przed wejściem wojsk radzieckich część mieszkańców zdążono ewakuować, pozostali doczekali się 27 stycznia 1945 r. wejścia Armii Czerwonej do Mikołajek. Zgodnie z postanowieniami konferencji pokojowych w Jałcie i Poczdamie, Mazury przypadły Polsce, co po okresie panowania krzyżacko-prusko-niemieckiego, było dla Mikołajek nowością. Do miasta zaczęła przybywać ludność napływowa z Kresów Wschodnich, przynosząc ze sobą na protestanckie dotąd tereny religię katolicką. Pojawiły się też polskie władze, organizujące państwowość na poniemieckich terenach, tzw. Ziemiach Odzyskanych.
