W dniach 5 i 6 czerwca 1991 r. Olsztyn znalazł się na pielgrzymim szlaku papież Jana Pawła II. Ojciec Święty wylądował na lotnisku w Dajtkach i przejechał do Seminarium w Redykajnach, gdzie spędził noc. Następnego dnia rano odwiedził pacjentów Szpitala Dziecięcego. W Parku Kusocińskiego, przy stadionie papież odprawił mszę, podczas której tematem homilii było VIII przykazanie: Nie mów fałszywego świadectwa przeciwko bliźniemu swemu. Pobyt w Olsztynie zakończyła wizyta w konkatedrze Św. Jakuba, po czym Jan Paweł II udał się na lotnisko i odleciał helikopterem do Włocławka.

25 marca 1992 r. Jan Paweł II ustanowił nowy podział kościelny na terytorium Polski. Istniejąca od 1243 r. diecezja warmińska została podniesiona do godności metropolii, biskup Edmund Piszcz uzyskał godność arcybiskupa. Archidiecezji warmińskiej przypisana została zwierzchność nad nowoutworzonymi diecezjami elbląską i ełcką.

Na przełomie XX/XXI w. odsłonięto kilka nowych pomników. W 1996 r. staraniem Towarzystwa Miłośników Olsztyna przywrócono figurę Św. Jana Nepomucena na moście jego imienia. W 2002 r. odsłonięto wznoszoną od 1997 r. kolumnę Orła Białego na Pl. Konsulatu Polskiego. W 2003 r. zaś w krajobrazie Olsztyna pojawiła się Ławeczka Kopernika, przy wejściu na groblę do zamku a na Pl. Solidarności odsłonięto pomnik Wolności Ojczyzny. Rok 2004 przyniósł figurę Św. Jakuba, która upiększyła Targ Rybny. W 2006 r. w 15 rocznicę mszy papieskiej mieszkańcy Olsztyna na placu celebry tejże mszy ustawili tablice pamiątkowe. 17 września 2009 r. w Kortowie otwarto Aleję Ofiar Katynia i pod przewodnictwem Prezydenta RP Lecha Kaczyńskiego zasadzono katyńskie dęby pamięci.

W latach 1996-2003 toczył się remont Starego Ratusza, podczas którego odkryte zostały gotyckie elewacje skrzydła południowego. Detale architektoniczne zostały zakonserwowane, przywrócono mu oryginalny kształt dachu i skrzydło to pozbawiono od stron zewnętrznych otynkowania. W 2000 r. na kalenicy dachu ponownie zamontowano wieżyczkę jeszcze bez zegara, ale nawiązującą do tradycji wyglądu Starego Ratusza.

Reforma administracyjna, która weszła w 1999 r. ustanowiła województwo warmińsko-mazurskie ze stolicą w Olsztynie. Przywrócone zostały zlikwidowane w 1975 r. powiaty, miasto Olsztyn stało się powiatem olsztyńskim grodzkim, tereny dookoła Olsztyna z miastami: Barczewo, Biskupiec, Dobre Miasto, Jeziorany i Olsztynek utworzyły powiat olsztyński ziemski.

Jubileusz 650-lecia miasta, obchodzony w 2003 r. przyniósł dyskusję o wyglądzie flagi miejskiej, wzmiankowanej w źródłach jeszcze w XIX w. Wybrano projekt niebieskiej flagi z zaznaczoną białą wstęgą symbolizującą rzekę i żółtą muszlą. Flaga od początku wzbudzała kontrowersje.

14 marca 2008 r. aresztowany został prezydent Olsztyna Czesław Jerzy Małkowski w związku z oskarżeniami o molestowanie seksualne podwładnych i gwałt na ciężarnej kobiecie. 16 listopada 2008 r. w referendum olsztynianie zagłosowali za odwołaniem prezydenta z urzędu.

21 lutego 2010 r. do Olsztyna przybyły szczątki Mikołaja Kopernika. Wystawiono je w olsztyńskiej archikatedrze a 16 marca 2010 r. przeniesiono na zamek, w którym Kopernik spędził kilka lat swojego życia. Z Olsztyna wyruszą na ponowny pogrzeb w archikatedrze Wniebowzięcia Najświętszej Marii Panny we Fromborku, który odbędzie się 22 maja 2010 r.