Primeras iniciativas de organización
La evangelización latina de la región cobró nuevo impulso después de la expansión del reino de Polonia hacia los territorios de Halicz y Vladímir. El rey Casimiro III promovió ante la Santa Sede la creación de varias sedes latinas en lugares donde existían comunidades cristianas orientales, entre ellas Przemysl, Halicz, Chelm, Vladímir, Lutsk, Kiev y Leópolis. Franciscanos y dominicos comenzaron entonces una actividad misionera estable en la zona.
En 1353, el papa designó como obispo a Nicolás Ruteno, prior dominico de Sandomir, y declaró la diócesis directamente sometida a la Santa Sede. La pobreza de la sede dificultó inicialmente la residencia habitual del obispo en la ciudad. Tras la muerte de Nicolás, el obispo de Lebus intentó recuperar competencias sobre Przemysl; Gregorio XI nombró en 1377 a Eric de Winsen, considerado el primer obispo efectivo de la sede.
Consolidación medieval
La diócesis quedó integrada en la reorganización latina de las estructuras eclesiásticas de la Europa centro-oriental. La actividad de las órdenes mendicantes contribuyó a la predicación, la administración de los sacramentos y la formación cristiana de la población.
Entre las figuras relacionadas con la historia eclesial de la región destaca el beato Jacobo Strepa, franciscano que defendió la labor de franciscanos y dominicos frente a acusaciones de invalidez sacramental formuladas por sectores del clero secular. Más tarde, como arzobispo de Halicz, intervino en la resolución de antiguas disputas entre las sedes de Halicz y Przemysl.
Przemysl en la monarquía de los Habsburgo
Tras las particiones de Polonia, la diócesis de Przemysl quedó incorporada a los territorios austríacos de Galitzia. Durante este periodo, la sede formó parte de la organización eclesiástica latina vinculada al arzobispado de Leópolis. La historia de Galitzia mantuvo una estrecha relación entre las jurisdicciones latinas y las comunidades católicas orientales, aunque cada una conservó su propio rito, disciplina y estructura jerárquica.
La antigua organización latina de la región tuvo como metrópoli a Leópolis, de la que Przemysl figuró como diócesis sufragánea junto con Tarnów.