Obecna ulica Olsztyńska, przed II wojną światową składała się z trzech odcinków – od Mickiewicza do Pułaskiego była to Kasernenstrasse (później Ludendorffstrasse), od Pułaskiego do Drwęckiej Gartenstrasse, a dalej Sendenhaupstrasse. Zanim cała ulica została Olsztyńską, podobno jej fragment tuż po wojnie nosił imię Kościuszki.

Przed II wojną światową, dzisiejsza ulica Drwęcka składała się z trzech ulic. Od skrzyżowania z ulicą Kopernika do przejazdu kolejowego Hindenburg Strasse, dalej Friedrich Strasse do Placu Tysiąclecia, a później do ulicy Olsztyńskiej Drewenz Strasse.

Przed II wojną światową zwała się Pausenstrasse czyli Pauzeńska. Po 1945 roku na krótko była ulicą Odrodzenia, by potem na długi czas zostać ulicą Duboisa. Prawie nikt z mieszkańców Ostródy nie wymawiał tej nazwy prawidłowo – powinno się mówić „dibua”, ale ostródzianie nazywali tę ulicę „dubojsa”.

Do 1933 roku, obecna ulica Jana Pawła II nazywała się Seminarstrasse czyli Seminaryjna, ponieważ przy tej ulicy, w miejscu gdzie obecnie znajduje się „Galeria Mazurska”, stał okazały budynek seminarium nauczycielskiego. Mimo tego, że w 1945 roku był tylko lekko uszkodzony, został rozebrany, a cegły, jak mówią mieszkańcy Ostródy pamiętający tamte czasy, pojechały na odbudowę stolicy. Po dojściu nazistów do władzy ulicę nazwano Adolf-Hitler-Strasse. Po 1945 roku nazwę ulicy przemianowano na Melchiora Wańkowicza. Pisarz dość krótko patronował tej ulicy. Prawdopodobnie w 1947 roku nazwano ją 1 Maja. Przez długie lata wyruszały stamtąd pochody pierwszomajowe. W 1991 roku zmieniono nazwę ulicy na Jana Pawła II.

Przedwojenna Wilhelmstrasse, po II wojnie światowej podobno nosiła nazwę Kilińskiego, a później Daszyńskiego. W kolejnych latach znana była jako Obrońców Stalingradu. Obecną nazwę otrzymała w 1991 roku.

Obecna ulica Sienkiewicza przed II wojną światową nazywała się Schillerstrasse. Początek bierze od skrzyżowania z ulicami Czarnieckiego i Jana Pawła II i prowadzi na wschód do ulicy Drwęckiej.