Budova starej školy, pravdepodobne najstaršia školská budova v meste, stojí vedľa evanjelického Chrámu Svätej Trojice, medzi Kolégiom a rímskokatolíckym farským kostolom sv. Mikuláša.

Stará mestská škola, dnes Knižnica P.O.HviezdoslavaNapriek absencii písomných správ, existenciu mestskej školy možno v Prešove predpokladať od prvých rokov 15. storočia. Už r. 1415 uvádzajú totiž matriky viedenskej univerzity prvého študenta z Prešova. Najstaršia známa zmienka o škole v mestskom archíve je z r. 1429.

Vysokú úroveň školy v stredoveku dokazuje štúdium viacerých jej absolventov na rôznych európskych univerzitách (Viedeň, Krakov, talianske univerzity). Silný impulz pre jej ďalší vývin znamenalo prijatie Lutherovej reformácie v 30. rokoch 16. storočia. Na jej čelo sa dostali vzdelaní rektori, absolventi nemeckých univerzít. Pri výuke vhodne aplikovali nové progresívne metódy vyučovania a takisto mesto začalo vzdelaniu venovať väčšiu pozornosť. Prvým z týchto rektorov bol Melanchtonov žiak Žigmund Gelei zo sedmohradskej Tordy, ktorý podnikol základné kroky k reformovaniu školy na humanistických princípoch. V jeho diele pokračoval Lukáš Fabinus, autor prvej tlačou vydanej učebnice u nás a po ňom známy spisovateľ, „poeta laureatus caesareus“ Ján Bocatius.

Za rektorátu Jána Serediho v prvej polovici 17. storočia mohla sa už škola právom pýšiť titulom „Celeberrimum Gymnasium“. Takisto ďalší rektori, Jakub Jakobeus, Samuel Dürner či Ján Bayer, budovali školu podľa vzoru evanjelických humanistických gymnázií v Nemecku. Niektorí senátori, profesori a maďarský farár György Curiani zamýšľali povolať za rektora J. A. Komenského, ktorý tu pobudol niekoľko dní r. 1651 a neskôr vysoko hodnotil úroveň mestskej školy. V polovici storočia pôsobili na gymnáziu významní filozofi Ján Bayer a Izák Caban, zakladatelia tzv. Prešovskej filozofickej školy.

Po postavení Kolégia a začatí pravidelnej výučby r. 1667 mestská škola zanikla. Naďalej však predstavovala majetok evanjelickej cirkvi v meste, a preto ju r. 1671 habsburské vojsko skonfiškovalo. Od roku 1673 v nej bolo umiestnené jezuitské gymnázium, pôsobiace s prestávkami (1682-1685,1705-1710) až do rozpustenia rádu r. 1773. Potom prešlo pod správu minoritov, kde bolo až do ich zrušenia cisárom Jozefom II. r. 1786. Zaniklo r. 1789 a obnovili ho až františkáni začiatkom nasledujúceho storočia. Od poslednej tretiny 19. storočia bolo pretvorené na štátne katolícke gymnázium a r. 1889 sa presťahovalo do novej budovy (dnes stredná pedagogická škola). Budova starej mestskej školy slúžila v minulosti rôznym účelom, v súčasnosti je v nej Knižnica P. O. Hviezdoslava.

Podoba pôvodnej školskej budovy z 15. storočia nie je známa. V r. 1519-1521 dala mestská rada na jej mieste postaviť novú, pod vedením majstra Petra Itala. Bola to jednoposchodová trojtraktová stavba na obdĺžnikovom pôdoryse, zdobená štítkovou atikou, so vstupným portálom na východnom priečelí a schodišťom na západnej strane hlavného traktu. V priebehu 18. storočia viackrát vyhorela a utrpela i ďalšie škody. Niekoľkokrát bola preto prebudovaná, najradikálnejšie po veľkom požiari r. 1887, keď došlo k zmene jej dispozície, premiestneniu schodišťa, pristavaniu druhého poschodia a celkovej úprave fasády v novorenesančnom štýle.