Początkowo wraz z dzisiejszą ulicą 1 Maja tworzyła Szosę Dobromiejską (Guttstadter-Chaussee, Szosa Gutsztacka), która następnie została podzielona na ulicę Dobromiejską (Guttstädterstrasse, ulica Gutsztacka, dzisiejsza ul. 1 Maja) i ulicę Królewską (Königstrasse, dzisiejsza al. Wojska Polskiego)Plan turystyczny Olsztyna, wydawnictwo Pharus-Verlag, 1925 rok. Przed II wojną światową na krótko zmieniono nazwę ulicy Królewskiej na Adolf-Hitler-Allee (aleja Adolfa Hitlera). Nazwa Aleja Wojska Polskiego została nadana w 1945 roku.
Plac położony naprzeciwko dzisiejszej Polikliniki przed 1945 rokiem nosił nazwę Georg-Zillch-Platz (plac Georga Zillicha). Po II wojnie światowej nie nadano mu nazwy.
Przy ul. Królewskiej (alei Wojska Polskiego) znajdowała się zajezdnia tramwajów konnych, a później tramwajów elektrycznych, która została zlikwidowana wraz z likwidacją komunikacji tramwajowej.
Do lat 90. XX wieku przy alei Wojska Polskiego 13 znajdowało się Kino Grunwald, które zostało zlikwidowane z powodów finansowych.