Op internationaal gebied leek er na 1953 iets van ontspanning te komen. De positie van Oostenrijk werd op 15 mei 1955 ondanks het verzet van de hardliner Molotov geregeld in een staatsverdrag: de bezettende machten trokken zich terug in ruil voor de toezegging van Oostenrijks neutraliteit. Chroesjtsjov herstelde de relatie met Joegoslavië. Ook werd in 1955 in Genève de eerste topontmoeting van de Grote Vier sinds Potsdam gehouden. Er werden weinig concrete resultaten geboekt, maar het feit dat er gepraat werd, getuigde van een zekere rust en stabiliteit. De eerste uitwisselingen tussen Oost en West op het gebied van wetenschap, sport en cultuur kwamen voorzichtig op gang. Deze uitwisselingen maakten echter wel deel uit van een propaganda-offensief waarbij het gehalte aan vaderlandslievendheid van in Moskou tentoongestelde Amerikaanse kunstwerken tot in het Congres toe in de gaten werd gehouden.
Langzaam maar zeker wist Chroesjtsjov, die zijn machtsbasis in de partij had, zijn rivalen weg te werken: Malenkov werd minister voor de elektriciteitscentrales en Molotov werd ambassadeur in Mongolië. Chroesjtsjov was een heel ander figuur dan Stalin, maar ook hij had iets onberekenbaars. Door de amnestie na de dood van Stalin waren veel politieke gevangenen vrijgelaten. De verhalen over de terreur onder Stalin deden de ronde. Chroesjtsjov vond dat dit hardop uitgesproken moest worden. Als de partij eenmaal gezuiverd zou zijn van deze smet op haar blazoen, zouden de mensen weer vertrouwen in de partij kunnen stellen. Hij zocht draagvlak om dit op het komende partijcongres aan de orde te stellen. Op dit partijcongres zouden veel vrijgelaten gevangenen aanwezig zijn. Zijn collega’s haalden hem over om het punt aan de orde te stellen in een besloten zitting.
Op 25 februari 1956, kort na middernacht, begon Chroesjtsjov aan een vier uren durende toespraak. Alleen de officiële gedelegeerden uit de Sovjet-Unie waren aanwezig. Waar de besloten zitting precies over zou gaan, was niet van te voren aangekondigd. In zijn toespraak nam hij uitdrukkelijk afstand van Stalin, van zijn terreur en van zijn misdaden. Hij verzweeg de slachtoffers die hij zelf in de Oekraïne bij de collectivisering van de landbouw op zijn geweten had, en maakte Stalin met de grond gelijk. Stalin had zich schuldig gemaakt aan een persoonlijkheidscultus. Stalin had in de partij een slachting aangericht. Van de 139 leden van het Centrale Comité die op het 17e partijcongres in 1934 gekozen waren, waren er 89 tijdens de zuiveringen doodgeschoten. Van de 1966 afgevaardigden naar dat partijcongres waren er 1108 uit de weg geruimd. De uitwassen werden aan de kaak gesteld. Chroesjtsjov hanteerde echter het fileermes en niet de botte bijl: het systeem zelf werd niet ter discussie gesteld. Het ging om wat Stalin de communistische partij had aangedaan: hij had de erfenis van Lenin bezoedeld. De talloze slachtoffers die Stalin onder de bevolking van de Sovjet-Unie als geheel gemaakt had, bleven ongenoemd.
De buitenlandse gasten kregen een dag later de gelegenheid om van de toespraak kennis te nemen. De toespraak raakte breed verspreid (opzettelijk? De kwalificatie “zeer geheim” was vervangen door: “niet voor publicatie”) en kwam via de Israëlische geheime dienst in handen van de CIA, die haar na verificatie doorspeelde aan de pers (de officiële publicatie in de Sovjet-Unie vond pas plaats in 1989). Voor veel congresgangers in Moskou stortte door de toespraak een wereld in. In Georgië, Stalins geboortestreek, ontstonden onlusten: er vielen 300 doden en 1.000 gewonden. Het Centraal Comité maakte eind juni duidelijk dat het Sovjetsysteem zelf niet ter discussie stond. De toespraak trok wereldwijd aandacht. De Chinezen waren woedend omdat zij niet van te voren op de hoogte waren gesteld. Mao zag Chroesjtsjovs kritiek op de persoonlijkheidscultus rond Stalin als kritiek op zichzelf. Het was het begin van de verwijdering tussen de Volksrepubliek China en de Sovjet-Unie. Maar ook Mao liet tijdelijk de teugels iets vieren: op een partijcongres zei hij dat honderd bloemen moesten bloeien en dat diverse gedachtestromen met elkaar moesten wedijveren. De partijleiders in Oost-Europa hielden hun hart vast: zij, de “kleine Stalins”, hadden hun positie voor een deel aan Stalin te danken. Maar de bevolking zag kansen voor verandering: zou er eindelijk ruimte ontstaan voor pluriformiteit binnen het socialisme?
De eerste onrust deed zich voor in Polen. De Poolse leider Bierut was kort na de toespraak van Chroesjtsjov in Moskou aan een hartaanval overleden. Hij werd opgevolgd door Ochab. Deze liet 30.000 politieke gevangenen vrij; ook de bij de arbeiders geliefde leider Gomulka, die vanwege nationalistische revanchistische opvattingen in 1948 aan de kant gezet was, kreeg weer bewegingsvrijheid. Ochab verleende vermindering van straf aan 70.000 gevangenen. De toespraak over Stalins wandaden werd op veel plaatsen besproken en leidde bij de bevolking tot kritiek op de Poolse partijleiding. Deze had eerst de toespraak laten vertalen en drukken. Toen de kritiek losbarstte, werd de toespraak alleen nog maar aan de partijfunctionarissen verstrekt. Maar het was al te laat. Exemplaren van de vertaalde toespraak kwamen via de zwarte markt bovendrijven. Informanten weigerden nog langer met de geheime politie samen te werken. Op 28 juni 1956 brak in een locomotievenfabriek in Poznan een staking uit. De stakers eisten loonsverhoging en betere economische omstandigheden, maar de demonstraties liepen uit op een eis tot meer vrijheid. Ten koste van 73 doden en vele honderden gewonden slaagde de Poolse regering er in met behulp van het leger orde en rust te herstellen. De regering dreigde met strenge strafmaatregelen maar erkende wel dat de stakers een punt hadden en dat er iets moest gebeuren. De VS probeerde in troebel water te vissen door via het Internationale Rode Kruis voedselhulp aan te bieden. Het aanbod werd afgeslagen. Ook Radio Free Europe probeerde de rellen uit te buiten. De vervolging van de stakers liep in de rechtbank uit op een protest tegen het systeem. De volkswoede zou alleen maar kunnen worden afgekocht als Gomulka in ere werd hersteld en de leiding weer kreeg. Ochab was bereid een stap opzij te doen.
Op 19 oktober, de dag dat het Poolse Politbureau Gomulka zou verkiezen, landden in Warschau onverwacht twee vliegtuigen uit Moskou. Chroesjtsjov en zijn collega’s kwamen – met twaalf generaals in vol ornaat in hun kielzog – poolshoogte nemen en eisten op hoge toon toegang tot de vergadering. Dit werd geweigerd. De Polen maakten duidelijk dat ingrijpen door Sovjet-strijdkrachten op daadwerkelijk verzet van Poolse legereenheden zou stuiten. Onder hoge druk kwam de afspraak tot stand dat de vergadering (en de verkiezing) door zouden gaan, maar daarna verdaagd zou worden voor nader overleg. Het bleek in dit nadere overleg mogelijk om aan de behoefte aan hervormingen tegemoet te komen zonder het politieke monopolie van de communistische partij aan te tasten. Gomulka drong wel aan op een minder vooraanstaande rol van Sovjet-“adviseurs” in Polen, maar vroeg niet om het vertrek van de Sovjet-strijdkrachten uit Polen. Hier vielen immers een Sovjet-belang (goede verbindingen met de grote troepenmacht in de DDR) en een Pools belang samen: de aanwezigheid van Sovjet-strijdkrachten in Polen zou garanderen dat er aan de nieuwe westelijke grens van het land geen ruimte zou komen voor Duits revanchisme. De Sovjet-strijdkrachten maakten door hun aanwezigheid wel inbreuk op de territoriale integriteit van Polen, maar garandeerden deze integriteit tegelijkertijd ook.
Chroesjtsjov en zijn metgezellen vlogen op 20 oktober weer naar Moskou terug. Helemaal gerustgesteld waren zij nog niet, maar zij wisten dat China moeite zou hebben met een Sovjet-ingreep in Polen. Bovendien was de situatie in Hongarije ernstiger en vroeg meer aandacht. Gomulka werd ongemoeid gelaten. Op 24 oktober betuigde een demonstratie in Warschau van 400.000 Polen haar steun aan hem. Hij bleef zich, ook vanwege het Poolse eigenbelang, opstellen als loyale bondgenoot. Hij voerde de noodzakelijke politieke en economische hervormingen langzaam door. Kardinaal Wyszynski kwam op 28 oktober op vrije voeten. Omdat de Sovjets hun eisen voor leveranties verlaagden, kreeg de Poolse economie meer lucht. De bevolking nam Gomulka het lage tempo van de hervormingen niet kwalijk. Zij meende dat hij wel sneller zou willen, maar dit vanwege de druk uit Moskou niet kon. Langzaam maar zeker werd Polen omgevormd. Voor zo’n geleidelijke omvorming waren de spanningen in Hongarije te groot. Daar ontstond een tragedie.