W roku 1956 przez Polskę przetoczyła się fala niepokojów politycznych, związanych z panującą w bloku wschodnim „odwilżą” po śmierci Józefa Stalina. Akcje nowego I sekretarza KPZR i przywódcy ZSRR, Nikity Chruszczowa, budziły nadzieje na znaczne złagodzenie systemu i powstrzymanie represji politycznych. Dodatkowym bodźcem do zmian w Polsce stała się niespodziewana śmierć Bolesława Bieruta, 12 marca 1956 roku. Społeczeństwo zaczęło coraz bardziej otwarcie domagać się zmiany „kursu” politycznego, złagodzenia represji i zwiększenia standardu życia, dotąd będącego na drugim planie na korzyść rozwoju przemysłu.
Kumulowane napięcie społeczne i dążenia społeczne doprowadziły w czerwcu 1956 do wybuchu niepokojów, później zaś regularnych walk w Poznaniu, gdzie doszło do starć milicji i wojska z protestantami. Mimo nałożonej przez władze blokady informacyjnej stawało się jasne, że nastroje tego typu będą jedynie narastać. Stąd też Partia musiała znaleźć nowe rozwiązanie i chociaż częściowo zgodzić się na ustępstwa.
Symbolem polskiej „odwilży” było wybranie na nowego I sekretarza PZPR Władysława Gomułki (21 października 1956 roku), którego wybór stał się symbolem zmian i złagodzenia polityki wewnętrznej, tzw. „Polskiego Października”. Gomułka był uważany przez wielu za postać sympatyczną, cieszył się dużym poparciem społecznym, co najciekawsze, za „zasługę” poczytywano mu jego przeszłość w więzieniu (w latach 40. w wyniku intrygi Bieruta został skazany na pobyt w więzieniu za „odchylenie nacjonalistyczne”). Liczono na to, że nowy sekretarz doprowadzi do szerszych zmian w polityce. Istotnie, już wkrótce rozpoczął się proces rehabilitacji wielu więźniów politycznych. Więzienia w dużej mierze opustoszały, wiele osób uniewinniono, inne zrehabilitowano pośmiertnie. Do władzy doszła ekipa komunistów chcących budowy socjalizmu „z narodowym” charakterem, stąd też delikatna zmiana akcentów w propagandzie (należy jednak pamiętać, że Polski socjalizm tego okresu nie był nawet w połowie tak niezależny jak chociażby komunizm albański czy jugosłowiański. Władze PRL ciągle operowały jedynie w ramach granic narzuconych przez ZSRR).
Oprócz złagodzenia aparatu przymusu doszło też do symbolicznego gestu, jakim było usunięcie z armii radzieckich oficerów, którzy od końca wojny jako „doradcy” sprawowali nad nią faktyczną kontrolę. Do ZSRR został odesłany marszałek Konstanty Rokossowski, dotąd pełniący funkcję wodza naczelnego. Gomułka obiecał zwiększenie roli przemysłu spożywczego i zapełnienie półek artykułami pierwszej potrzeby, wyrównanie potrzeb przemysłu ciężkiego i lekkiego. Wszystkie te gesty i działania złożyły się na ostateczny koniec i demontaż stalinowskiego systemu w Polsce.