W okresie wczesnośredniowiecznym na terenie Mikołajek znajdowało się grodzisko. Była to najprawdopodobniej siedziba pruskiego plemienia Galindów. Świadczą o tym odkryte w pobliżu miasta kurhany. W 1444 roku powstała wieś kościelna – na mocy przywileju wielkiego mistrza krzyżackiego Konrada Bon Erlichshausena, który nadał Wawrzyńcowy Prusowi 15 włók ziemi na prawie magdeburskim. Wieś swą wzięła od św. Mikołaja patrona wzniesionego na wzgórzu kościoła katolickiego. Początkowo funkcjonowało tu zaledwie kilkanaście gospodarstw. Obszar zaczął rozwijać się dopiero na przełomie XV i XVI w., kiedy to zaczęli osiedlać się na tych terenach koloniści polscy z Mazowsza. W 1539 roku zamieszkiwali tu prawie sami Polacy. W 1656 roku na wieś najechali Tatarzy.
W 1726 roku Mikołajki otrzymały prawa miejskie. Nadał je król pruski Fryderyk Wilhelm I. W skład miasta weszły trzy odrębne dotąd osady: Koniec, Mikołajki i Kozłowo. Jeszcze w 1516 roku wybudowano drewniany most, który je połączył. Pierwszy burmistrz nazywał się Kopeć, a miasto składało się z trzech okręgów: rynku Końca i przedmieścia Kozłowa.
XVIII w. to ciężki okres w historii miasta. W 1729 roku miał miejsce wielki pożar. W 1758 r. podczas wojny siedmioletniej Mikołajki zajęli Rosjanie. Zmusili wszystkich urzędników i duchownych do złożenia przysięgi wierności carycy Elżbiecie. 9 lat później wielkich szkód dokonał huragan. Miasta nie oszczędziła również panująca dżuma.
Pierwsza połowa XIX w. to ponownie okres dotkliwych klęsk w życiu miasta, które nawiedzały często pożary, epidemie cholery, nieurodzaje i susze. Skutkiem tych ostatnich były długie lata głodu.
W 1843 r. wprowadzono regularne rejsy parowca Masovia na trasie Ryn – Mikołajki – Pisz. W 1911 r, poprowadzono przez Mikołajki linię kolejową Orzysz – Mrągowo. Przed I Wojną Światową liczba ludności liczyła 2291 osób. W 1939 r. liczba ludności wzrosła do 2627. Podczas II Wojny Światowej zniszczono 20% miasta.