同时，尽管苏联的统治长期笼罩着东欧，卫星国一直是难以控制的。1948年南斯拉夫起义，而该国是所有东欧新兴共产主义国家中最听话的一个。南斯拉夫是在第一次世界大战刚结束时，在哈布斯堡和奥斯曼帝国的残骸上建立的，它在1941年推翻了亲德政府。二战期间，它一直是以游击战的形式打击德国和意大利。共有两大集团在攻打外来侵略者，而他们之间也并不友好。切特尼克代表塞尔维亚皇室，东正教控制着南斯拉夫帝国南部；游击队由铁托领导。在苏联的支持下，游击队占了上风并在1944年开始统治南斯拉夫。

随后，当权的铁托建立了共产党执政政府，取缔了君主制度。他用了三年时间，积极地接受了所有主要的苏联政策，涉及政治、经济和文化等方面。同时他还坚持奉行自己的政策。1948年6月，在莫斯科的支持下，铁托政府被驱逐出共产党情报局——这是苏联掌控的欧洲共产党组织。苏联的卫星国取消了与南斯拉夫的经济协议，加强反铁托的宣传，掀起与南斯拉夫的各种边境纠纷。斯大林相信他可以完全压制南斯拉夫。“我动一动小手指，”他说，“铁托就再也不存在了。”

美国立刻利用铁托倒台这一事件。为了更深地破坏苏联集团，华盛顿向南斯拉夫提出援助，铁托即刻就答应了。在他的领导下，南斯拉夫共产党开始了自己的事业，放弃了冷酷、神秘、高度集权的斯大林模式。权力下放从经济开始，鼓励适当参与当地政府、贝尔格莱德?中央政府以及南斯拉夫共产党的决策，这种共产主义形式令苏联政权极端厌恶。因为苏联奉行的是严格执行莫斯科的一切命令，普通党员要完全忠实于党的领导。受到铁托主义的威胁，苏联在东欧开始了对铁托支持者的大清洗，使希望尝试南斯拉夫模式的国家屈服。

与莫斯科不同是不好的，反对苏联统治就更加糟糕。1953年3月斯大林去世，苏联统治一片混乱。谁将继续铁腕领导？在过渡时期，莫斯科对苏联帝国的统治有多安全？一个并不受欢迎的答案在6月揭晓，东柏林的工人起义。三分之一的工人罢工，反对政府削减工资。示威者进而反对东德政府，要求民?选举、摆脱苏联控制。接下来的几年，在波兰、匈牙利、捷克斯洛伐克，类似的运动不断在苏联集团中爆发。苏联坦克驶上别国的大街，在当地警察的帮助下，游行被迅速镇压了，但可惜运动已经遍及全东德。军事法庭宣布，在运动中267人死亡，数千人被抓。责任在“法西斯主义者”、挑衅者和外在的煽动者。暴动后政府做出妥协，取消削减工资，并在一系列福利问题上做出让步，但共产党继续加强控制。例如，建立国民自卫队体系，在紧急情况下可以成为苏联的军事力量。通过这些手段，苏联要加强对1700万东德人的控制。

苏联领导人的继任危机并没有像东德起义这样快的平息。起初，权力斗争的结果是共同领导，几位有野心的领导人彼此监视。这种方式差点使政府瘫痪。最终，赫鲁晓夫打败了其他对手成为共产党第一书记，后又成为主席。他当书记后的行动之一就是与铁托言和，1955年5月他亲自到贝尔格莱德公开道歉。铁托与莫斯科的关系得到缓和，尽管南斯拉夫从没中断与西方民主国家的联系。赫鲁晓夫甚至宣称，在清除支持铁托分子时有很多受害者被误判了。但在承认这一切的同时，赫鲁晓夫又带来了新的麻烦。

1956年，赫鲁晓夫指责斯大林，并承认了过去苏联的不公正行为。这些举措更刺激了欧洲各卫?国。1956年6月，波兰波兹南的工人暴动之后，波兰其他地方也有巨大振荡，葛慕卡领导的一个共产党派系发动了这次起义。由于波兰新政府仍然是共产党执政，他们允许它存在，直到1970年。