Pisane dzieje Przemyśla sięgają X wieku, natomiast zręby pierwszych organów władzy miejskiej wiążą się z lokacją miasta na prawie magdeburskim. Wówczas też zaczyna się historia archiwum miejskiego.
Pierwsza wzmianka dotyczy roku 1635 a zasób zbiorów ukazuje burzliwe dzieje miasta oraz dokumentuje zróżnicowany skład wyznaniowy i narodowościowy mieszczan przemyskich. Dokumenty przechowywano najprawdopodobniej w Ratuszu a w czasie zaboru austriackiego zmieniono zasady archiwizacji dokumentów staropolskich, które zostały złożone w jednym z pomieszczeń magistratu i tam pozostawały do zajęcia budynku przez powstały w 1855 roku Sąd Obwodowy w Przemyślu.
W czasie I wojny światowej przemyskie archiwum wzbogaciło się o nowe zbiory, gdyż w lipcu 1916 roku pod auspicjami Polskiego Archiwum Wojennego w Wiedniu powołano Komitet Archiwum Wojennego w Przemyślu. Rok później opiekę nad archiwum przejmuje Towarzystwu Przyjaciół Nauk w Przemyślu w tym czasie zasoby archiwalne zostają uporządkowane według katalogu Błażowskiego.
W latach II wojny światowej większość zasobów archiwum było dwukrotnie wywożone z miasta. W 1940 roku zabrały go do Lwowa okupacyjne władze radzieckie, skąd wróciły do Przemyśla w 1943 po czym w roku 1944 za sprawą niemieckich władz okupacyjnych znalazły się w Tyńcu k/Krakowa i zostały odzyskane dopiero w roku 1947.
Po wyzwoleniu Polski organizacja zbiorów i podległość instytucjom państwowym ulega ciągłym zmianom a fatalne warunki lokalowe powodują, że władze miasta przeznaczają dla archiwum budynki pocerkiewne po OO. Bazylianach. Dzięki ustawie uchwalonej przez Sejm w 1989 roku, dającej możliwości roszczeń majątkowych Kościoła obrządku greckokatolickiego, OO. Bazylianie odzyskali w roku 1991 swoje budynki.
Staraniem władz miejskich udało się pozyskać budynek byłej pralni i łaźni miejskiej w Przemyślu przy ulicy Lelewela. Generalny remont obiektu pozwolił uzyskać obszerną powierzchnię dla zasobów i stworzył warunki do nowoczesnego ich zarządzania. Od 1996 roku Archiwum Państwowe w Przemyślu zajmuje właśnie ten budynek.