В развернувшейся борьбе Берия опирался на силовые ведомства, базой Маленкова было правительство страны, Хрущева — партийный аппарат. Политический вес партаппарата в то время был меньше не только веса Совета министров, но и МВД. О соотношении сил можно судить хотя бы по таким фактам: заработная плата уполномоченных госбезопасности на районном уровне была в 4 раза больше, чем у секретарей райкомов партии. У госчиновников квартиры были лучше, чем у партчиновников. О личном отношении лидера партноменклатуры к шефу МВД свидетельствует выразительная фраза, сказанная Хрущевым Н. А. Булганину сразу после смерти Сталина: «Если Берия получит госбезопасность, это будет началом нашего конца».
Борьба за лидерство стоила Берии жизни (декабрь 1953 г.). Она же привела к утрате завоеванных Маленковым (в феврале 1955 г. он потерял пост главы правительства), Молотовым (снят с поста министра иностранных дел в июне 1956 г.) позиций, разгрому так называемой антипартийной группы Маленкова, Кагановича, Молотова (июнь 1957 г.), отстранению Г. К. Жукова от руководства Вооруженными силами страны (октябрь 1957 г.). В марте 1958 г. Булганин смещен с поста председателя Совмина СССР. Хрущев, возглавив с этого времени два высших поста в партийно-государственном руководстве (1-го секретаря ЦК партии и председателя Совмина), стал единоличным лидером.
Сторонники Хрущева, пришедшие на освобожденные места в Президиуме ЦК и Совмине СССР, известными по сталинским временам методами пытались укреплять авторитет нового лидера. Удалось, однако, создать «культ без личности». Безудержное реформаторство Хрущева по большей части не давало плодов и заставляло сомневаться в его мудрости. Большой поддержки Хрущеву не могли оказать А. Н. Косыгин (с июля 1957 г. заместитель, с мая 1960 г. 1-й заместитель Предсовмина) и Л. И. Брежнев, избранный в мае 1960 г. Председателем Президиума ВС СССР вместо Ворошилова. Напротив, Брежнев оказался в итоге одним из организаторов заговора, положившего конец политической карьере Хрущева в октябре 1964 г.
Все отставки представлялись народу как следствие ошибок в определении и проведении нового курса внутренней и внешней политики государства.
С первых шагов новое руководство попыталось дистанцироваться от сталинской политики. Это проявилось уже 10 марта 1953 г., когда отчет о похоронах Сталина в «Правде» был оформлен в духе «культа». Речь нового главы правительства на траурном митинге набрана более крупным шрифтом, в газете опубликована сфальсифицированная фотография Маленкова, помещенного между Сталиным и Мао Цзедуном. В этой связи премьер заявил: «В прошлом у нас были крупные ненормальности, многое шло по линии культа личности. И сейчас надо сразу поправить тенденцию, идущую в этом направлении… Считаем обязательным прекратить политику культа личности!»
Однако вплоть до февраля 1956 г. официальное понятие «культа личности» и имя Сталина как бы не имели между собой ничего общего. В газетах, как и раньше, неизменно подчеркивалась его «неоценимая» роль в решении всех вопросов деятельности партии и государства. Например, в редакционной статье «Правды» от 14 января 1954 г. указывалось: «Ленинские программные указания по национальному вопросу нашли свое дальнейшее творческое развитие в произведениях великого продолжателя бессмертного дела Ленина — И. В. Сталина». Его «классические» статьи по национальному вопросу переиздавались до 1959 г.
Поражение Берии. Несмотря на то что сразу после смерти Сталина фигурой номер один в руководстве страны считался Маленков, фактически ведущую роль начал играть Берия. Он исходил из того, что главным звеном в послесталинском обществе по-прежнему должны оставаться силовые ведомства, к руководству которыми выдвигались его ставленники. Уже 19 марта 1953 г. были заменены руководители МВД во всех союзных республиках, 12 автономных областях, 6 краях и 49 областях России. Новые руководители в свою очередь проводили замену кадров в среднем руководящем звене. Органы госбезопасности имели решающее слово при любых выдвижениях или перемещениях партийных, государственных и хозяйственных кадров. Такая активность не могла не вызывать настороженности коллег Берии по Президиуму ЦК. Однако на первых порах они поддерживали Берию и его инициативы.
Первыми приказами новый министр создал следственные группы и комиссии по пересмотру дел, находящихся в производстве отделов и управлений МВД. Такие группы занимались делами «арестованных врачей», «бывших сотрудников МГБ», «работников Главного артиллерийского управления Военного министерства», по делам «о выселении граждан из Грузии», «по обвинению бывшего руководства ВВС и Министерства авиационной промышленности».