Wewnątrz miasta zbudowano 9 zespołów koszarowych, szpital wojskowy, szpital cywilny, a także areszt, który nosił nazwę Garnszus Arest, czyli Areszt Garnizonowy. Potocznie nazywano go budynkiem Schwarca. Pierwotne plany zakładały, że miał to być młyn zbożowy, ale władze zrezygnowały z tej koncepcji. Powstający areszt był ściśle związany z budową Twierdzy Przemyśl, a przyległe do niego budynki pełniły ważną funkcję w administracji garnizonu, który miał docelowo liczyć 85 tyś. żołnierzy.
W sąsiedztwie aresztu, usytuowanego przy ulicy Rokitniańskiej, znajdowały się Wojskowy Sąd Okręgowy, Wojskowy Sąd Rejonowy i Prokuratura Wojskowa. Budynki z racji swoich funkcji stanowiły pokaz sztuki budownictwa wojskowego i wojennego. Układ gmachów tworzył rodzaj miniaturowego miasta, posiadającego swoją własną wewnętrzną strukturę, która wynikała z wojskowych regulaminów. Sam areszt to gmach dwukondygnacyjny o mocnej konstrukcji, zbudowany ok. 1877/80r. w kształcie litery E.
Niestety z chwilą poddania Twierdzy (22 marca1915r.) zniszczono wszystkie dokumenty mogące cokolwiek powiedzieć o pierwotnej konstrukcji budynku oraz o stanie etatowym załogi i więzionych tu żołnierzach. Pewne wzmianki o działalności aresztu można znaleźć w przemyskim Archiwum Państwowym, gdzie przechowywane są nieliczne ocalałe dokumenty z tego okresu. Nie ulega wątpliwości, że w areszcie przetrzymywani byli żołnierze CK Armii oraz obywatele oskarżeni o pospolite przestępstwa. Oddzielną grupę stanowiły osoby aresztowane i skazane za szpiegostwo na rzecz Rosji lub podejrzane o tzw. rusofilstwo, czyli sprzyjanie i pomoc wrogowi. W więzieniu działali kapelani więzienni różnych wyznań udzielając skazańcom duchowego wsparcia.
Jarosław Haśek uwiecznił przemyski areszt w "Przygodach Dobrego Wojaka Szwejka”. To z kart tej książki dowiadujemy się jakie warunki sanitarne panowały w areszcie oraz jakie restrykcje i kary stosowano względem skazanych. W sposób humorystyczny natomiast ukazuje strażników więziennych ikary jakie na nich nakładano za wykroczenia dyscyplinarne.
Okres walk niepodległościowych i odradzania się państwa polskiego to szczególny okres w historii aresztu. Obiekt został przejęty przez władze polskie. Nastąpiła zmiana nazwy na Przemyskie Więzienie Garnizonowe.
W okresie tym areszt był wypełniony głównie skazanymi żołnierzami z armii austro-węgierskiej, których często osadzono za złamanie regulaminów wojskowych lub pospolite przewinienia o charakterze wykroczeń porządkowych. Władze polskie borykając się z trudnościami aprowizacyjnymi zwalniały część aresztowanych, głównie z pośród żołnierzy obcych państw (Czechów, Węgrów). Zatrzymaniu podlegali tylko pospolici przestępcy oraz osoby skazane prawomocnie za poważne przestępstwa kryminalne (zabójstwa, gwałty).
Również w okresie okupacji budynek pełnił rolę więzienia i tak jest do chwili obecnej. W tymokresie więzienie znajdowało się na terenie żydowskiego getta, a zachodni odcinek muru więziennego po swojej zewnętrznej stronie był miejscem straceń polskich patriotów. Miejsce to upamiętnia stosowna tablica oraz obelisk.