Prípravy na založenie Mestskej knižnice v Prešove sa začali v prvej polovici roku 1925. V októbri 1925 knižnicu slávnostne otvorili v neveľkej klenutej miestnosti na prízemí mestského domu, ktorú predtým užívali mestskí policajti. Knižný fond tvorilo 500 zväzkov od Matice slovenskej a 200 zväzkov od štátu.

Zakladateľ knižnice Belo Klein - Tesnoskalský však svojimi aktivitami presvedčil správu mesta, aby aj napriek veľkým nákladom zaobstarala pre knižnicu, už v roku 1926, jasnú priestrannú miestnosť v budove Čierneho orla, v susedstve čitárne Matice slovenskej.

Nástupcom Bela Kleina - Tesnoskalského bol v rokoch 1934 až 1954 v celoslovenskom knihovníctve známy PhDr. Jozef Repčák, ktorý sa vo veľkej miere zaslúžil o ďalší rozvoj knižnice.

Po roku 1945 bola knižnica prenesená do nových priestorov, kde mala dobre upravenú požičovňu, oddelenie pre mládež, priestrannú čitáreň a sklady kníh.

Z organizačnej stránky knižnica prešla istým vývojom. Po utvorení Prešovského kraja, koncom roku 1951 bola premenovaná na krajskú knižnicu. Postupne začali vznikať nové oddelenia a nové odborné pracoviská. Pozornosť sa venovala oddeleniu pre mládež, kde bol aj ako prvý zavedený voľný výber. Bolo vybudované metodické oddelenie, ktoré sa sústredilo na plánovitú prípravu a organizovanie školení knihovníkov, nezabúdalo sa pritom na vydávanie metodických a bibliografických materiálov.

Po územnej reorganizácii v roku 1960 utvorením Východoslovenského kraja sa stala okresnou knižnicou. Vybudovali sa nové pobočky na sídliskách v meste a postupne sa rozvíjala sieť ľudových knižníc v celom okrese.

Od 1.1.1991 sa knižnica stala štátnou príspevkovou organizáciou v riadení Ministerstva kultúry SR. V roku 1993 sa otvára nové oddelenie pre nevidiacich a slabozrakých a začína sa s automatizáciou knižnično - informačných služieb.

Od 1.7.1996 v rámci transformácie kultúry a na základe rozhodnutia Ministerstva kultúry sa knižnica stáva už len štátnym odborným útvarom Šarišského kultúrneho centra v Prešove. Knižnica stratila právnu subjektivitu a bola premenovaná na Šarišskú knižnicu. K zásadnej zmene ešte došlo 4.10.1996, kedy Ministerstvo kultúry delimitovalo Šarišské kultúrne centrum pod riadenie krajského úradu v Prešove. Nastáva zníženie rozpočtu a následný úbytok financií na knižný fond. Právnu subjektivitu knižnica opätovne získala až novou zriaďovacou listinou Krajského úradu v Prešove z 1.4.1999. Stala sa tak regionálnou knižnicou P.O. Hviezdoslava v Prešove.

V súvislosti s reformou verejnej správy od 1.4.2002 Knižnica P.O.Hviezdoslava prechádza pod nového zriaďovateľa Prešovský samosprávny kraj s pôsobnosťou a kompetenciami krajskej knižnice v súlade so zákonom O knižniciach č. 183 / 2000 Z.z