Początek rządów towarzysza Wiesława to czas liberalizacji i przywracania praworządności – również w relacjach z Kościołem katolickim i innymi wyznaniami. Związek był wyraźny: podczas najsłynniejszego (i, jak się miało okazać, końcowego) akordu Października, jakim był wiec na placu Defilad 24 października 1956 roku, obok „Stu lat" dla towarzysza Wiesława najgłośniej słychać było skandowanie „uwolnić Prymasa". Decyzje polityczne w tej sprawie I sekretarz podjął już wcześniej, teraz szło o to, by jak najprędzej uspokoić nastroje: już nazajutrz do Komańczy ruszają Władysław Bieńkowski i Zenon Kliszko, by 28 października przywieźć Stefana Wyszyńskiego do Warszawy.
Na początku grudnia odbyło się posiedzenie tzw. Komisji Wspólnej Rządu i Episkopatu, podczas którego podjęto przełomowe decyzje: uchylenie dekretu rządu z 9 lutego 1953 roku, na mocy którego – na miesiąc przed śmiercią Stalina – władze przyznały sobie prawo samodzielnego obsadzania stanowisk kościelnych. Uzgodniono uwolnienie uwięzionych duchownych, w tym najbardziej znanego, prócz Wyszyńskiego, biskupa Czesława Kaczmarka. Władze wyraziły zgodę na budowę nowych kościołów i przywrócenie nauczania religii w szkołach podstawowych i średnich.