W swojej historii Olecko miało jeszcze 2 inne nazwy. Najpierw w 1560 r., była to Margrabowa. Nazwa pochodziła od tytułu władcy Prus, księcia i zarazem margrabiego brandenburskiego, Albrechta Hohenzollerna. Od 1928 r. nosiło nazwę Treuburg.
Okolice Olecka przecina gęsta sieć strumieni łączących liczne jeziora. Działalność lodowca pozostawiła w gminie Olecko ślady w postaci 15 jezior. Większość z nich należy do wód otwartych i posiada charakter rynnowy. Od północnego zachodu gminę otacza Puszcza Borecka, która kryje w sobie rzadkie okazy roślin i zwierząt. Obfitość wód i lasów, walory turystyczno-krajoznawcze regionu oraz położenie na ważnych szlakach komunikacyjnych podnoszą atrakcyjność gminy. Występują tu tereny pagórkowate.
Najstarsze ślady pobytu ludzi na terenie wschodnich Mazur i ziemi oleckiej pochodzą sprzed 11 tys. lat p.n.e., czyli paleolitu. Okolice Olecka zasiedlała ludność tzw. kultury lyngbijskiej, której obozowiska zlokalizowano m.in. w Puchówce na terenie gminy Wieliczki. W połowie pierwszego tysiąclecia p.n.e. na obszar dzisiejszych Mazur przybyła ludność utożsamiana z Bałtami, której kulturę określano mianem kurhanów zachodniobałtyckich. Na podstawie wykopalisk można wnioskować, że już kilka tysięcy lat temu mieszkali tutaj ludzie.
Rozwój miasta hamowały klęski żywiołowe, takie jak pożary, epidemie oraz zniszczenia wojenne. Powodowały one straty materialne, znaczne ubytki ludności polskiego pochodzenia oraz niemal całkowite zniszczenie zabytków architektury. Duże zniszczenia przyniosły pożary w końcu XVII i na początku XVIII w., najazd tatarski w latach 1656-1657, epidemia dżumy, która w latach 1709-1711 pochłonęła na terenie ówczesnego starostwa oleckiego ok. 11 tysięcy osób (w samym Olecku ocalało zaledwie 78 osób) oraz obie wojny światowe.
W drugiej połowie XIX w. Olecko zaczęło się rozwijać dzięki budowie połączeń drogowych i kolejowych. W 1879 r. przez Olecko poprowadzono linie Ełk – Wystruć, a w 1908 r. uruchomiono połączenie z Giżyckiem. Olecko i najbliższe okolice miasta były miejscem krwawych walk niemiecko-rosyjskich w latach 1914-1915. Samo miasto było przez pewien czas okupowane przez wojska rosyjskie i doznało poważnych zniszczeń.
Plebiscyt w powiecie oleckim w 1920 r. zakończył się przytłaczającym sukcesem Niemiec. Z 28627 oddanych w powiecie głosów jedynie 2 padły za Polską.
21 stycznia 1945 r. miasto zostało zajęte przez wojska sowieckie. Sowieci spalili około 80% zabudowy.
