니키타 흐루쇼프 지도자로서(1956-1964)
위기가 전개되면서 미국에는 긴장감이 극에 달했다. 반면 소련에서는 흐루쇼프가 대중 앞에 여러 번 모습을 드러냈고 당시 모스크바에서 공연 중이던 제롬 하인스의 공연을 보기 위해 볼쇼이 극장에 방문하기도 했다. 10월 25일까지 소련에서는 케네디의 의도를 완전히 분명하게 알지 못했고, 흐루쇼프는 쿠바에서 미사일을 철수해야 한다고 결정했다. 이틀 후, 그는 케네디에게 쿠바 미사일 철수 조건을 제시했다. 흐루쇼프는 미국이 쿠바를 침공하지 않겠다는 약속과 소련의 심장부를 강타할 수 있는 터키의 미사일을 철수하겠다는 약속을 받고 쿠바의 미사일을 철수하는 것에 동의하였다. 흐루쇼프의 마지막 임기는 미국의 요청에 따라 발표되지 않았고, 1971년 흐루쇼프가 사망할 때까지 알려지지 않아 이러한 결정은 소련에게 큰 패배로 여겨졌고 2년 뒤 흐루쇼프의 축출에 크게 기여했다. 카스트로는 흐루쇼프에게 쿠바에 미군이 침공할 때, 핵미사일 선제 공격을 촉구했지만, 흐루쇼프의 결정에 분노하였다.
위기 이후, 케네디가 1936년 6월 10일, 아메리칸 대학교에서 화해 연설을 하면서 제2차 세계대전 중 소련 인민들의 고통과 그들의 업적을 인정했고, 양국 간의 관계는 개선되었다. 흐루쇼프는 이 연설을 프랭클린 D. 루스벨트의 연설 이후 미국 대통령이 한 최고의 연설이라고 불렀으며, 7월에는 미국의 윌리엄 애버렐 해리먼, 영국의 헤일샴 경과 부분적 핵실험 금지 조약에 서명하였다. 두번째 흐루쇼프-케네디 정상회담 계획은 1936년 11월 케네디의 암살로 인해 취소되었다. 새 미국의 대통령 린든 B. 존슨은 흐루쇼프와의 관계 개선이 지속되기를 희망했지만, 다른 여러 문제들 때문에 흐루쇼프가 축출되기 전까지 관계를 발전시키지 못했다.
흐루쇼프의 《비밀 연설》이 발표된 뒤, 폴란드의 지도자 볼레스와프 비에루트의 사망과 결합한 《비밀 연설》은 폴란드와 헝가리에서의 상당한 자유화를 촉발했다. 1956년 6월, 폴란드 포즈난에서는 노동자 파업이 소요 사태로 확대되어 50명 이상이 사망했다.
소련 모스크바의 정치인들은 소요 사태가 서방 선동가들의 탓으로 돌렸지만, 폴란드의 정치인들은 모스크바의 주장을 무시하고 노동자들에게 양보하였다. 폴란드에서 반소비에트적인 표현이 보편화되고 중요한 폴란드의 지도부 선거를 앞두자, 소련의 흐루쇼프와 상임위원들은 폴란드의 상임위원을 만나기 위해 10월 19일 바르샤바로 갔다. 소련은 소련-폴란드 관계에 지도부 교체가 큰 영향을 미치지 않을 것이라고 예상했고, 새 폴란드 지도부가 집권하는 것에 동의했다. 결국 폴란드에서는 '폴란드의 10월'로 알려진 부분적인 자유화가 진행되었다.
폴란드의 상황을 본 헝가리인들은 모스크바에 도전할 수 있다고 결정하여 대담해졌다.
결국 이는 10월 23일 부다페스트에서 대규모 시위가 대중적인 봉기로 확대되었다. 당 지도자들은 이에 대한 대응으로 너지 임레를 인민공화국의 수상으로 임명하였다. 도시에서 소련군은 헝가리군과 충돌했고 시위대에 발포하여 수백 명의 헝가리인/소련인이 죽었다. 너지 임레는 휴전과 소련군의 철수를 요구했고, 흐루쇼프가 이끄는 상임위원회는 새로운 헝가리 정부에게 기회를 주기로 결정하였다. 흐루쇼프는 모스크바에서 자유를 인정해주면 너지 임레가 소련과의 동맹을 고수할 것이라고 예상하였다.
10월 30일, 너지 임레는 다당제를 발표했고, 다음 날에는 바르샤바 조약 기구의 탈퇴를 선언했다. 11월 3일에, 너지 임레 정부의 두 구성원이 자칭 임시 정부의 수반으로 우크라이나를 방문하여 소련군의 개입을 요청하였다. 그 다음 날, 소련군은 헝가리 혁명을 진압하여 4000명의 헝가리인과 수백 명의 소련군이 사망하였다. 너지 임레는 체포되었고, 나중에 처형당했다. 혁명 개입에 대한 국제적인 분노에도 불구하고, 흐루쇼프는 자신의 행동을 변호했다. 이러한 개입에 대한 소련의 외교적 피해는 상당했으며, 세계의 관심을 빠르게 돌릴 수에즈 위기가 우연히 일어나지 않았으면 피해는 더 컸을 것이다.
이러한 외교적 위기의 여파로, 흐루쇼프는 자신이 후에 가장 기억에 남는다고 말했던 "Мы вас похороним!"(당신들을 묻어버리겠다!)라고 언급했다. 서방은 이러한 그의 언급을 위협으로 받아들였지만, 흐루쇼프는 서방과 평화로운 공존에 관한 연설에서 이러한 말을 언급했다. 1959년에 미국을 방문했을 때, 이 언급에 대한 질문을 받았는데, 이 때 흐루쇼프는 "말 그대로 묻어버리는 것이 아닌 냉혹한 역사적 발전을 통해 공산주의가 자본주의를 대체하고 자본주의를 묻어버릴 것"이라고 뜻한 것을 밝혔다.
1948년 스탈린이 자신이 유고슬라비아의 지도자 요시프 브로즈 티토를 통제할 수 없음을 깨달은 이후, 흐루쇼프는 완전히 단절되었던 유고슬라비아와의 관계를 회복시켰다. 1955년 흐루쇼프는 소련 대표단을 이끌고 베오그라드로 갔다. 소련에 적대적이었던 티토는 대표단을 공개적으로 취하게 하는 것을 포함하여 소련이 어리석어 보이도록 하게 했음에도, 흐루쇼프는 관계를 따뜻하게 하게 하여 소련-유고슬라비아 관계의 인폼비로 기간(Informbiro)을 끝냈다. 헝가리 혁명 동안 티토는 처음에 너지 임레를 지원했지만, 후반기에 흐루쇼프의 개입의 필요성을 들며 그를 설득하려 하였다. 그러나, 소련의 헝가리 개입은 소련-유고슬라비아 관계를 손상시켰으며, 흐루쇼프는 이를 회복시키기 위해 몇 년을 보냈다. 그는 중화인민공화국이 유고슬라비아의 자유주의적 공산주의를 인정하지 않았다는 점에 방해를 받았고, 양국의 관계를 화해시키려는 시도는 분노한 베이징 지도부를 낳았다.
1949년 마오쩌둥은 중국 본토를 모두 장악한 후, 소련에게 물질적 지원을 요청하면서 러시아 제국 시절 차르에 의해 빼앗긴 영토의 반환을 요구했다. 몇년 뒤, 흐루쇼프가 소련을 장악했고, 그는 중국에 대한 원조를 늘리고 새로운 공산주의 국가의 발전을 위해 소규모 전문가 집단을 보내기까지 했다. 역사가 윌리엄 C. 커비는 이러한 기술적 지원을 '세계 역사상 가장 위대한 기술 지원'이라고 묘사했다. 소련은 1954년부터 1959년 사이에 중국에 대한 국가 원조가 국민 소득의 7%를 차지하기도 하였다. 1954년에 흐루쇼프가 중국을 방문했을 때, 뤼순항과 다롄의 반환에 동의했지만, 마오쩌둥이 소련 대표단이 돌아갈 때 포병을 데려가라는 주장을 하자 화가 났다.
마오쩌둥은 유고슬라비아와 같은 보다 자유주의적인 동유럽 국가와 화해하려는 흐루쇼프의 시도를 격렬히 반대하였다. 하지만 흐루쇼프는 적극적인 세계적 혁명 운동에 대한 마오쩌둥의 열망에 대해 주저했으며, 공산주의의 생활 수준을 높여 자본주의를 정복하는 것을 선호했다.
두 나라의 관계는 1956년 급속히 차가워지기 시작했다. 마오쩌둥은 《비밀 연설》에 대해 중국과 협의하지 않았다는 사실에 분노했고, 그는 탈스탈린화가 실수이며 자신의 권위에 위협이 될 수 있다고 생각했다. 1958년 흐루쇼프가 중국을 방문했을 때, 마오쩌둥은 군사 협력 제안을 거부했다. 흐루쇼프의 노력이 헛수고로 돌아가는 것을 희망한 마오쩌둥의 행보는 제2차 타이완 해협 위기를 낳았고, 마오쩌둥은 중국의 포격을 받은 타이완의 섬들을 "아이젠하워와 흐루쇼프를 춤추게 하고 이리저리 움직이게 하는 지휘봉"이라고 묘사하였다.
원래 소련은 중국에게 완전한 문서가 포함된 핵무기를 제공할 계획이었지만, 1959년 냉담한 관계 속에서 이러한 계획을 파기하였다. 흐루쇼프가 미국을 방문한 해 9월, 그가 중국을 방문했을 때에 쌀쌀한 환대를 받았고, 방문 계획은 7일이었지만, 흐루쇼프는 3일만에 중국을 떠났다. 또한, 1960년 루마니아 당 대회를 서로를 공격할 기회로 판단하고 이용한 소련과 중국의 행동으로 인해 양국의 관계는 더욱 악화되었다. 흐루쇼프가 당 대회에서 중국을 공격한 이후, 중국의 정치가 펑전은 흐루쇼프의 외교 정책이 서방을 뜨겁게 불사르는 것이라고 조롱했다. 이에 흐루쇼프는 중국에 있는 소련이 파견한 전문가들을 데려오는 것으로 대응했다. 알바니아는 중국과 소련의 분쟁 속에서 흐루쇼프를 알바니아식 반공 농민의 이름을 따서 '라포 렐로'(Rrapo Lelo)라고 묘사하면서 중국의 편에 섰다.