Na przełomie lat pięćdziesiątych i sześćdziesiątych, dzięki skutecznym zabiegom prymasa Wyszyńskiego, ilość nowo utworzonych parafii powiększyła się w 1967 roku do 56. Powstawały najczęściej w miejscowościach, dokąd wierni mieli łatwy dojazd a nabożeństwa sprawowano w porozumieniu z biskupami diecezjalnymi i proboszczami. Liturgie mogły być odprawiane w kościołach rzymskokatolickich. W październiku 1958 roku prymas Wyszyński udzielił szesnastu księżom greckokatolickim prawa do wykonywania czynności liturgicznych i duszpasterskich wchodzących w zakres praw i obowiązków proboszczów.

Władze tolerowały posunięcia prymasa, ale pod warunkiem, iż nie będą wymagały one regulacji cywilno-prawnych. Na utworzenie nowego duszpasterstwa greckokatolickiego, oprócz akceptacji wszystkich szczebli władz państwowych, potrzebna była zgoda poszczególnych instancji łacińskiej administracji kościelnej. Zdarzały się przypadki, kiedy prymas aprobował rozpoczęcie działalności a lokalne władze oraz miejscowy ordynariusz lub proboszcz byli temu przeciwni. Dzięki ogromnej determinacji i stałej komunikacji prymasa z referentami udawało się uzyskać niezbędne pozwolenia wszystkich stron, co w praktyce przynosiło pozytywne efekty, gdyż współpraca duchownych i wiernych dwóch obrządków na ogół układała się pomyślnie.

Mimo osiąganych kompromisów, w zależności od konkretnych sytuacji, aktywizacja działalności duszpasterskiej księży greckokatolickich wywoływała niepokój służb bezpieczeństwa, które próbowały różnymi sposobami ograniczać otwieranie nowych ośrodków. Wywierano naciski na duchownych obu obrządków, których wzywano na przesłuchania, próbując ich w taki sposób zastraszyć i zniechęcić. W tym czasie nie udawało utrzymywać kontroli nad całością podjętych przez prymasa przedsięwzięć, gdyż zdarzały się sytuacje, iż w jednym regionie Polski nasilały się ograniczenia ze strony władz, a w innej części kraju wzmagały się apele ze strony wiernych, dotyczące legalizacji działalności duszpasterskiej Kościoła greckokatolickiego.

Niezmiernie istotną sprawą dla rozwoju duszpasterstwa była kwestia kształcenia nowych kadr. Początkowo kandydaci do kapłaństwa okazjonalnie kształcili się w seminariach diecezjalnych dla łacinników, z czasem jednak prymas Wyszyński wyznaczył w tym celu podległe jego jurysdykcji seminarium gnieźnieńskie a w roku 1964, po rozmowie z lubelskim biskupem Piotrem Kałwą, zgodził się, aby chętni mogli kształcić się i otrzymywać formację w wyższym seminarium duchownym w Lublinie. O przynależności kościelnej greckokatolickich kleryków wiedział tylko ordynariusz i wychowawcy, gdyż służby peerelowskie bacznie śledziły rozwój sytuacji i stale nalegały na rozwiązanie takiej współpracy. Nie udało im się jednak złamać rektorów i ich współpracowników, dzięki czemu w ciągu półwiecza ukończyło seminarium ponad stu kapłanów greckokatolickich, wzbogaconych doświadczeniem współpracy międzyobrządkowej w ramach jednego Kościoła katolickiego.

Proces reorganizacji struktur greckokatolickich, prowadzony przez kard. Wyszyńskiego, był na bieżąco współkoordynowany przez ks. Bazylego Hrynyka, który zajmował się poszukiwaniem księży rozproszonych po całym kraju oraz kontaktem z wiernymi. Pełnił rolę łącznika, szukając rozwiązań w zapewnieniu posługi duszpasterskiej w rodzimej tradycji. Było to niezwykle trudne zadanie, gdyż grekokatolicy, pozbawieni osobowości prawnej, zostali w praktyce ubezwłasnowolnieni. Prymas nawiązywał bezpośrednie kontakty z biskupami diecezjalnymi w sprawie możliwości zorganizowania duszpasterstwa dla grekokatolików przy parafiach rzymskokatolickich. Ze względu na dyskryminacyjną politykę władz komunistycznych Kościół greckokatolicki nie mógł samodzielnie prowadzić działalności, dlatego potrzebował wsparcia hierarchów i duchowieństwa rzymskokatolickiego, którzy również borykali się z ogromnymi trudnościami. Pomimo przykrych doświadczeń we wzajemnych relacjach w okresie II wojny światowej było wielu biskupów i kapłanów otwartych na współpracę, którzy odważnie wspierali i bronili praw grekokatolików do swobodnego zaspokajania potrzeb religijnych we własnym obrządku, dzięki czemu zdobyli sobie ogromny szacunek i wdzięczność.