Początki archiwum miejskiego w Przemyślu sięgają średniowiecza i wiążą się z lokacją miasta na prawie magdeburskim oraz powstaniem pierwszych organów władzy w mieście: rady i ławy miejskiej. Zachowany z okresu staropolskiego zasób aktowy odzwierciedla burzliwe dzieje miasta oraz dokumentuje zróżnicowany skład wyznaniowy i narodowościowy mieszczan przemyskich. W latach 1874-1877 Mieczysław Błażowski opracował „Katalog starożytnego Archiwum Królewskiego Miasta Przemyśla”, stanowiący do dziś źródło cennych informacji o dziejach i zawartości archiwaliów staropolskich. W czasie I wojny światowej archiwum przemyskie wzbogaciło się o nowe zbiory, gdyż w lipcu 1916 r. powołano Komitet Archiwum Wojennego w Przemyślu, będący delegaturą Polskiego Archiwum Wojennego w Wiedniu. Akcja podjęta przez tą instytucję oraz ówczesnego archiwariusza miejskiego, Tadeusza Troskolańskiego, doprowadziła do zgromadzenia druków, książek, pamiętników, prasy w języku polskim, ukraińskim i niemieckim dotyczących sprawy polskiej w czasie I wojny oraz historii oblężonej twierdzy w Przemyślu. W 1917 r. Magistrat miasta powierzył opiekę nad Archiwum Towarzystwu Przyjaciół Nauk w Przemyślu. Pierwszą archiwistką z ramienia TPN była dr Maria Polaczkówna. Po jej wyjeździe z Przemyśla Zarząd TPN postanowił powierzyć opiekę nad archiwum miejskim Janowi Smołce. Uporządkowane przez Smołkę archiwum miejskie otrzymało nowy układ, którego podstawą był katalog Błażowskiego (pominął akta z pierwszej połowy XIX w., które praktycznie były niedostępne dla badaczy). Efektem tych prac był wydany w 1927 r. "Katalog Archiwum Aktów Dawnych Miasta Przemyśla". W 1935 r. TPN przeniosło za zgodą Magistratu Archiwum Aktów Dawnych Miasta Przemyśla do pomieszczeń w budynku przy ul. Władycze 7. Polepszyło to warunki przechowywania archiwaliów i umożliwiło w większym stopniu jego udostępnienie badaczom miejscowym i przyjezdnym. Wybuch II wojny światowej przerwał działalność TPN, a tym samym doprowadził do powrotu archiwum miejskiego pod opiekę miasta.

Zarządzeniem Ministra Oświaty z 10 listopada 1950 r. zostało powołane Wojewódzkie Archiwum Państwowe w Rzeszowie. Archiwum miasta Przemyśla po włączeniu go do państwowej sieci archiwalnej w czerwcu 1951 r. zostało podporządkowane WAP w Rzeszowie. Otrzymało ono nazwę Wojewódzkie Archiwum Państwowe w Rzeszowie Oddział w Przemyślu. Trudne warunki lokalowe WAP w Rzeszowie spowodowały przeniesienie go do Przemyśla, w którym zostało utworzone Wojewódzkie Archiwum Państwowe w Rzeszowie z siedzibą w Przemyślu. Równocześnie został zlikwidowany oddział w Przemyślu, a w miejsce WAP w Rzeszowie utworzono Oddział terenowy. Dyrektorem WAP, w Rzeszowie z siedzibą w Przemyślu został docent Kazimierz Arłamowski. Warunki lokalowe WAP lepsze od rzeszowskich nie zaspokajały jednak potrzeb nowo powołanego archiwum. Podjęte starania doprowadziły do uzyskania od władz miejskich w styczniu 1961 r. budynku pocerkiewnego po OO. Bazylianach przy ul. PCK 4. Po przejściu na emeryturę dyrektora Kazimierza Arłamowskiego w roku 1970 przeniesiono siedzibę WAP do Rzeszowa, natomiast w Przemyślu utworzono Oddział Terenowy, którego kierownikiem została mgr Wanda Kaput, a po jej wyjeździe do Krakowa Aurelia Dziedziuk. Utworzenie w 1975 r. województwa przemyskiego, a także dobra baza lokalowa archiwum, bogaty zasób, tradycje ośrodka kulturalnego i naukowego, były podstawą powołania zarządzeniem nr 4 Ministra Nauki, Szkolnictwa Wyższego i Techniki z 21 stycznia 1976 r. Wojewódzkiego Archiwum Państwowego w Przemyślu, obejmującego swym zasięgiem obszar województwa przemyskiego. Funkcję p.o. dyrektora powierzono Aurelii Dziedziuk, od 1 sierpnia 1976 r. funkcję dyrektora przejął dr Zdzisław Konieczny. Dzięki jego staraniom w roku 1977 Prezydent miasta Przemyśla przekazał Archiwum dodatkowe pomieszczenia byłego klasztoru przy cerkwi OO. Bazylianów. Ustawa o stosunku do Kościoła Katolickiego w PRL uchwalona przez Sejm w 1989 roku stworzyła możliwości roszczeń majątkowych Kościoła obrządku greckokatolickiego. Skorzystali z niej OO. Bazylianie, zgłaszając swe roszczenia Komisji Majątkowej w Warszawie, która decyzją z 1 października 1991 r. orzekła zwrot byłej cerkwi i klasztoru OO. Bazylianom. Dzięki poparciu m.in. przemyskich organizacji, Prezydenta Miasta Przemyśla, Wojewody Przemyskiego udało się archiwum uzyskać budynek byłej pralni i łaźni miejskiej w Przemyślu. W rezultacie remontu trwającego od 1992 do 1996 roku Archiwum Państwowe w Przemyślu uzyskało budynek odpowiadający wymogom archiwalnym. Uroczyste otwarcie nowej siedziby miało miejsce w lipcu 1996 roku.

Archiwum Państwowe w Przemyślu, w swoim zasobie, przechowuje archiwalia wytworzone w okresie książat ruskich, okresie staropolskim, następnie pod panowaniem Habsburgów, okresie zaborów, II Rzeczypospolitej, II wojny światowej z okupacji radzieckiej i niemieckiej oraz wytworzone po 1945 r. Zmiany ustrojowe po 1989 r.  powodujące likwidację wielu urzędów wiążą się z przyjmowaniem do zasobu archiwalnego akt najnowszych.

Największy a zarazem cenny źródłowo zespół stanowią dokumenty z archiwum biskupstwa greckokatolickiego, obejmującego chronologicznie okres od końca XIII w. aż do likwidacji diecezji obrządku wschodniego w 1946 r. Coraz większym zainteresowaniem, nie tylko historyków, ale też demografów i genealogów cieszą się księgi metrykalne obrządku greckokatolickiego z poszczególnych dekanatów eparchii przemyskiej, a także zachowane w szczątkowym stanie metryki gmin żydowskich, ewangelickich i parafii rzymskokatolickich.