Pewne zmiany dokonywały się w rządzie, który próbował się uwolnić spod kurateli Biura Politycznego i odzyskać samodzielność w zakresie polityki ekonomicznej. Do tej pory o polityce tej decydowała PKPG. „Była ona wówczas jeszcze nadal rządem w rządzie i decydowała nie tylko o strategii gospodarczej państwa - mówił Cyrankiewicz w 1986 r. - ale uprawiała coś w rodzaju ręcznego sterowania (…). Dążyłem wtedy, mam na myśli wiosnę 1956 r., do odzyskania kontroli nad PKPG, ale jeszcze nie było żadnych rozstrzygnięć. Współpracowałem w tym celu z wybitnymi ekonomistami. Niestety i wtedy i później ich zdanie nie przeważało (…)”.

Na 23 kwietnia zaplanowano sesję sejmu. Bezpośrednio przed jej otwarciem 19 kwietnia odwołano S. Radkiewicza ze stanowiska ministra PGR i W. Sokorskiego ze stanowiska ministra kultury i sztuki. 20 kwietnia odwołano prokuratora generalnego PRL Stefana Kalinowskiego, naczelnego prokuratora wojskowego gen. S. Zarako-Zarakowskiego i wielu prokuratorów. 22 kwietnia odwołano ministra sprawiedliwości H. Świątkowskiego i wiceministra H. Cieśluka. Następcą Sokorskiego został Karol Kuryluk, Świątkowskiego - Zofia Wasilkowska, a Radkiewicza - gen. M. Moczar. Prokuratorem generalnym został Marian Rybicki. 23 kwietnia aresztowano gen. R. Romkowskiego i płk. A. Fejgina z b. MBP.

Premier Cyrankiewicz, przemawiając w sejmie w dniu 23 kwietnia, mógł się pochwalić. Mówił o trudnej sytuacji ekonomicznej związanej ze stanem wykonania planu 6-letniego i przygotowaniach do planu 5-letniego oraz dążeniach władz do demokratyzacji stosunków w Polsce. Premier mówił o „odwilży” i jej następstwach. Po exposé doszło po raz pierwszy w tej kadencji sejmu do autentycznej dyskusji; zgłoszono interpelacje poselskie.

27 kwietnia uchwalono ustawę o amnestii. Obejmowała ona różne grupy przestępstw. W sprawach o przestępstwa polityczne przewidywała ona darowanie kary pozbawienia wolności do 5 lat, łagodziła o połowę kary więzienia od 5 do 10 lat oraz o 1/3 powyżej 10 lat. Kary dożywotniego więzienia zamieniała na karę 12 lat, a karę śmierci na karę 15 lat więzienia. Szacowano, że amnestia obejmie około 80 tys. ludzi. Do 22 maja więzienia opuściło około 35 tys. osób, w tym 4,5 tys. więźniów politycznych.

Wiele osób uwolnionych nie czuło się usatysfakcjonowanych. Żądano zadośćuczynienia moralnego. Powołano komisje rehabilitacyjne, które przeglądały poszczególne sprawy i rehabilitowały niesłusznie skazanych. Już 28 kwietnia uchylono wyrok w sprawie procesu generałów z lipca 1951 r., ponieważ stwierdzono, że „dowody na których oparto skazanie tych osób uzyskane zostały na skutek stosowania niedopuszczalnych metod śledztwa”.

Dyskusja obejmowała swym zasięgiem coraz szersze kręgi i miała coraz głębszy charakter. W dniu 29 IV 1956 r. K. T. Toeplitz ogłosił w „Nowej Kulturze” artykuł pt. „Z własnego prawa bierz nadanie”. Autor kwestionował prawo PZPR do sprawowania władzy w Polsce, pisał o rewolucji ludowej, o nowych prawach. Część członków KC ostro krytykowała niektórych członków BP i żądała rozliczenia osób odpowiedzialnych za nadużycia władzy.

Pod naciskiem opinii oddolnej Biuro Polityczne KC PZPR podjęło dyskusję nad sprawą Bermana. Do tego czasu zasłaniał się on sytuacją ogólną, naciskiem Berii itp. Popierała go większość członków BP. Jednak 3 maja uznano, że powinien on opuścić zajmowane dotąd stanowisko. Sądzono, że w ten sposób złagodzona zostanie krytyka kierownictwa w całości. 4 V 1956 r. Berman poprosił o zwolnienie go z obowiązków członka Biura Politycznego i wicepremiera rządu. Po Bierucie była to druga osobistość minionej epoki. Pozostawali jeszcze Minc, Mazur i Zambrowski, jeśli nie liczyć samego Ochaba. Berman był tu swego rodzaju kozłem ofiarnym. Poświęcono go wobec ataków podejmowanych ze strony tzw. Grupy Natolińskiej. W okresie tym w KC zarysował się podział na tzw. Natolińczyków i Puławian.

Pierwszą z nich tworzyła grupa działaczy związkowych i przemysłowych. Przewodniczący CRZZ Wiktor Kłosiewicz już w czasie słynnej narady centralnego aktywu partyjnego w listopadzie 1954 r. żądał wyjaśnienia sprawy Gomułki i rozliczenia ludzi odpowiedzialnych za łamanie praworządności. „Jeżeli Gomułka jest winien - mówił Kłosiewicz - to trzeba mu wytoczyć sprawę, a jeżeli nie ma przeciwko niemu udowodnionych zarzutów, to trzeba go uwolnić”. Gomułka został uwolniony 13 XII 1954 r., ale pozostawał poza partią. Kierownictwo PZPR do jesieni 1956 r. nie wiedziało, co dalej z nim zrobić.

Na III Plenum KC w styczniu 1955 r. Kłosiewicz negatywnie ocenił samokrytykę Bermana, który próbował zrzucić z siebie odpowiedzialność za łamanie praworządności w Polsce na Berię i ZSRR. Krytykował też przesunięcie Radkiewicza z MBP do PGR, wzywał do ukarania całego kierownictwa MBP, polemizował z wysuniętą przez Minca tezą głoszącą jakoby w 1954 r. płace robotnicze w Polsce wzrosły o 12%. Na podstawie danych CRZZ Kłosiewicz dowiódł, że nastąpił nie wzrost, lecz spadek stopy życiowej mas pracujących.

Z podobnymi tezami i wnioskami wystąpili Bolesław Rumiński i Mieczysław Popiel. Wszyscy trzej zostali też ostro skarceni przez Bieruta, który w podsumowaniu obrad wystąpił w obronie Bermana i Minca. Natomiast Rokossowski w czasie przerwy podszedł do Kłosiewicza i pogratulował mu „bolszewickiego” stanowiska. Gest ten poważnie zaszkodził Kłosiewiczowi w opinii innych członków KC. „Wówczas to zaczęło się mówić - pisze Kłosiewicz - że określeni towarzysze w łonie KC występują z własną platformą propagandową. Zwolenników tego stanowiska, które przedstawiłem na III Plenum, zaczęto określać mianem grupy natolińskiej. Już wtedy dała się odczuć wyraźna zmiana stosunku wielu członków KC do mojej osoby (…)”.

Nazwa grupa natolińska wzięła się od pałacyku CRZZ w Natolinie, gdzie Kłosiewicz spotykał się ze swoimi zwolennikami. W czasie VI Plenum KC 20 III 1956 r. Kłosiewicz sprzeciwiał się kandydaturze R. Zambrowskiego na sekretarza KC. Wystąpienie jego kilka osób zrozumiało jako antysemickie. Od tego momentu natolińczyków klasyfikowano jako stalinowców, przeciwników reform, nacjonalistów, antysemitów itp. Do Kłosiewicza, Rumińskiego i Popiela przyłączyli się Stanisław Łapot, Zenon Nowak, Kazimierz Witaszewski.

Drugą grupę tworzyli członkowie KC zamieszkali w Warszawie przy ul. Puławskiej 24/26. Byli to na ogół ludzie powiązani z dawnym ścisłym kierownictwem partii, ludzie pochodzenia żydowskiego, dobrze zorientowani i dobrze sytuowani. Zmierzali oni do takiego ukierunkowania dyskusji, by odpowiedzialność za zbrodnie minionej epoki zrzucić na czynniki zewnętrzne. Ostro krytykowali Stalina, kult jednostki i ZSRR, wzywali do liberalizacji stosunków. Czołową rolę odgrywał wśród nich Roman Zambrowski, obok niego działali I sekretarz Warszawskiego Komitetu PZPR Stefan Staszewski i Leon Kasman. Współpracowali z nimi tzw. młodzi sekretarze KC: Albrecht, Matwin i Morawski. Spowodowali oni rozluźnienie cenzury, ułatwili druk referatu Chruszczowa o Stalinie, sprzyjali ujawnieniu różnych spraw kompromitujących ZSRR, prowadzili ostrą polemikę z Natolińczykami nazywając ich stalinowcami, antysemitami, nacjonalistami, antyinteligentami itp. Puławianie mieli w swym ręku prasę i posiadali duże możliwości urabiania opinii publicznej. Ujawniali różne szczegóły z tajnych posiedzeń BP i KC, które ułatwiały im kompromitację przeciwników.

Wiosną 1956 r. prasa polska zamieszczała interesujące materiały. W niektórych krajach socjalistycznych wstrzymano jej rozpowszechnianie. Kraje te nie publikowały referatu Chruszczowa, nie dopuszczały też do wielkich dyskusji ideologicznych. Prasa polska była ciekawsza. W Moskwie po „Trybunę Ludu” ustawiały się do kiosku kilometrowe kolejki. Jeden egzemplarz czytało wiele osób.

Zdecydowana większość członków KC nie miała jasno sprecyzowanego stanowiska. W walce wewnątrzpartyjnej nie angażowała się ani po jednej, ani po drugiej stronie. „Nadal - pisze Sokorski - nie należałem do żadnej »frakcji«. »Natolin« ode mnie stronił, uważając mnie za liberała. »Puławska« widziała we mnie „goja”, który trąci nacjonalizmem. Dla zwykłych ludzi byłem po prostu „Ruskim”, maruderem spod Lenino, może inteligentnym, ale bez przyszłości”.

W dalszym ciągu dokonywano zmian w rządzie. 27 kwietnia odwołano Stanisława Skrzeszewskiego ze stanowiska ministra spraw zagranicznych. Na stanowisko to powołano Adama Rapackiego. Na opróżnione przez niego stanowisko ministra szkolnictwa wyższego powołano Stefana Żółkiewskiego. Zwolnione przez Bermana stanowisko wicepremiera 4 maja objął Eugeniusz Stawiński. W czerwcu i lipcu kilka resortów skasowano. 11 lipca E. Szyra odwołano ze stanowiska przewodniczącego PKPG. Stanowisko to objął S. Jędrychowski.