Ujadanie psów, tętent końskich kopyt, szczęk żelaza i głośne rozmowy zapowiadały powrót dostojników z udanego polowania. Na czele gromady widać dwie postacie. Czapki z głów – to król polski August i książę pruski Albrecht von Hohenzollern! Czy rzeczywiście tak było? Nie wiemy, ale jest to prawdopodobne.
Przy wschodnim brzegu Jeziora Oleckie Wielkie na nasłonecznionej skarpie w połowie XVI wieku znajdowały się budy myśliwskie (Jagdbude) o nazwie Oletzko. Według historyka Krzysztofa Hartknocha to miejsce 7 września 1544 r. odwiedził książę Albrecht Hohenzollern (Markgraf Albrecht der Ältere von Brandenburg). W 1560 r. w czasie polowania spotkał się z królem Polski Zygmuntem Augustem. Według legendy postanowiono wtedy, że zostanie założone miasto Margrabowa, a po drugiej stronie granicy Augustów. To miejsce do XIX wieku nazywane było przez mieszkańców „Dworczyska”.
Przez stulecia mieszkańcy opowiadali legendę o tajemniczym tunelu prowadzącym pod jeziorem do „Dworczyska”. W celu wyjaśnienia tej sprawy w 1919 r. władze Olecka skierowały pismo do Towarzystwa Historycznego w Królewcu. Tajemnica nigdy nie została wyjaśniona.
Pierwsza wzmianka o planie założenia nowego miasta w starostwie straduńskim znajduje się w memoriale zatytułowanym “Co Henryk Kroszel i Krzysztof Szafstedt powinni wymierzyć w węgorzewskiem” 7 października 1559 r.. Kroszel był starostą Kłajpedy, Krzysztof von Krösten Szafstedt — starostą W Taplakach. Obaj oni otrzymali polecenie udania się razem z mierniczymi w okolice Stradun w celu dokonania różnych pomiarów i dokładnego przeprowadzenia badań terenowych. Niebawem też znaleźli miejsce położone nad Jeziorem Oleckim Wielkim aby wymierzyć i przeznaczyć pod kolonizację część puszczy w starostwie straduńskim. Na wykonanych przez nich szkicach (przechowywanych w bibliotece w Berlinie) widoczny jest zarys jeziora, budy myśliwskie i miejsce gdzie ma być miasto.
Olecko uzyskało prawa miejskie w 1560 roku jako Margrabowa. Po wytyczeniu dużego rynku (powierzchnia ponad 5,5 ha) wybudowano kościół ewangelicki i ratusz. Powolny rozwój miasta spowodowany był znacznym oddaleniem od ważniejszych szlaków handlowych oraz zniszczeń wojennych nękających Olecko w XVII i XVIII wieku: wojny szwedzkie (w 1656 roku Polacy odnieśli zwycięstwo nad kwaterującymi tu Szwedami), w latach 1656-1657 najazd tatarski, w 1757 roku wkroczenie wojsk rosyjskich.
Pod koniec XVIII wieku nastąpił znaczny rozwój miasta (w granicach państwa pruskiego). W drugiej połowie XIX i na początku XX wieku powstawał drobny przemysł.
Od 17 sierpnia 1914 r. na terenie powiatu oleckiego toczyły się intensywne działania wojenne po ataku wojsk rosyjskich na Prusy Wschodnie. Od 30 września do 2 października 1914 r. doszło do zaciętych walk pod Raczkami, gdzie Niemcy powtórnie powstrzymywali ataki Rosjan. 12 lutego 1915 r. wojska rosyjskie wycofały się z Olecka.
W wyniku plebiscytu w 1920 roku miasto pozostało w granicach Niemiec, a od 1928 do 1945 roku nosiło nazwę Treuburg (Wierny Gród). Ponowny okres dynamicznego rozwoju nastąpił w dwudziestoleciu międzywojennym. Miasto rozwijało się jako prężny ośrodek turystyczny, sportowy i rekreacyjny.
W czasie II wojny światowej miasto uległo znacznemu zniszczeniu (szacowanemu na ok. 60%). Całkowitej likwidacji uległ przemysł, jak również sieć kolejek wąskotorowych.
Od 1945 roku miasto znalazło się w granicach Polski – w latach 1946-1975 było siedzibą powiatu.
W wyniku reformy administracyjnej od stycznia 1999 r. Olecko jest ponownie miastem powiatowym.