Początki archiwum miejskiego zaczęły się w czasach lokacji miasta na prawie magdeburskim. W 1635 roku odnotowano istnienie Archiwum miejskiego (archiwum civile), tworzone dokumenty miejskie przechowywano w siedzibie Rady miejskiej (od 1563 roku w Ratuszu).

W czasie zaboru Austriackiego dokumenty archiwalne zostały umieszczone w magistracie, a od 1855 roku w Sądzie Obwodowym (akta miejskie połączono z aktami sądowymi). Sytuacja ta trwała do 1874 roku, gdy akta miejskie zwrócono miastu. Pierwszym archiwariuszem miejskim został Mieczysław Błażowski, który w latach 1874-1877 opracował Katalog starożytnego Archiwum Królewskiego Miasta Przemyśla. W 1916 roku powołano Komitet Archiwum Wojennego w Przemyślu (Delegatura Polskiego Archiwum Wojennego w Wiedniu). W 1917 roku opiekę nad archiwum zaczęło sprawować Towarzystwo Przyjaciół Nauk w Przemyślu, wówczas rozpoczęto udostępniać zbiory archiwalne dla badaczy i historyków. Za czasów archiwariusza Jana Smołki przeprowadzono pierwszą konserwację akt i poczyniono prace porządkowe.

W 1927 roku wydano Katalog Archiwum Aktów Dawnych Miasta Przemyśla. W 1835 roku Towarzystwo Przyjaciół Nauk przeniosło siedzibę archiwum do budynku przy ul. Władycze. Podczas II wojny światowej archiwum powróciło pod opiekę miasta. W 1940 roku archiwum zostało przez sowietów wywiezione do Lwowa, skąd w 1944 roku przez Niemców zostało wywiezione do Tyńca. Zbiory archiwalne dopiero w 1947 roku powróciły do Przemyśla.

W czasie powojennym archiwum wzbogaciło się o nowe akta z terenu Województwa Rzeszowskiego. 10 listopada 1950 roku zarządzeniem Ministra Oświaty zostało powołane Wojewódzkie Archiwum Państwowe w Rzeszowie. W 1951 roku archiwum miejskie zostało przejęte przez państwo jako Oddział zamiejscowy w Przemyślu, jednak z powodu trudności lokalowych Wojewódzkie Archiwum w Rzeszowie zostało przeniesione do Przemyśla. Następnie utworzono oddziały terenowe w: Jaśle (1952), Tarnobrzegu (1953), Sanoku (1954) i Przeworsku (1961). W 1961 roku uzyskano dla archiwum budynek po cerkiewny oo. Bazylianów.

W 1970 roku siedzibę Wojewódzkiego Archiwum Państwowego przeniesiono do Rzeszowa, a w Przemyślu utworzono oddział terenowy. Po powstaniu województwa przemyskiego 21 stycznia 1976 roku zostało utworzone Wojewódzkie Archiwum Państwowe w Przemyślu. W 1991 roku komisja majątkowa w Warszawie orzekła zwrot budynku Bazylianom, dlatego w 1996 roku na siedzibę archiwum zaadaptowano nowy budynek. Po utworzeniu województwa Podkarpackiego, archiwum funkcjonuje pod obecną nazwą Archiwum Państwowe w Przemyślu. Po wprowadzeniu systemu komputerowego i digitalizacji, archiwum udostępnia swoje zbiory poprzez publikację skanów on-line.