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ł się dworek myśliwski (Jagdbude) o nazwie Oletzko. Prawdopodobnie w tym miejscu w 1544 r. książę Albrecht Hohenzolern (Markgraf Albrecht der Ältere von Brandenburg) spotkał się w czasie polowania z królem Polski Zygmuntem Augustem. Według legendy postanowiono wtedy, że zostanie założone miasto Marggrabowa (Olecko) a po drugiej stronie granicy Augustów.
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.