В апреле 1950 года Сталин сделал Булганина первым заместителем в правительстве.
Хрущев потом вспоминал:
— Я помню, как мы с товарищем Кагановичем полетели к товарищу Сталину в Сочи, он там тогда отдыхал. Были у него несколько дней и вели разговоры на разные темы… Товарищ Сталин поднял такой вопрос: стар, говорит, что вы меня, старика, эксплуатируете… Он спрашивал: кого можно избрать председателем Совета министров? И он сказал: я бы считал подходящим на этот пост товарища Булганина. Сейчас давайте утвердим его первым заместителем председателя Совета министров.
Отныне повседневная власть сосредоточилась в руках тройки — Берия, Маленков, Булганин. И первые двое сделали всё, чтобы подорвать позиции Николая Александровича.
— Когда Сталин назвал Булганина как возможную кандидатуру на пост председателя Совета министров, — рассказывал Хрущев, — всё было мобилизовано против Булганина. И создалось такое впечатление, что, когда председательствует на Совете министров Булганин, никакой вопрос нельзя было решить. Берия его не поддерживает, Маленков его не поддерживает… Как бы ни был вопрос хорошо подготовлен, можно сказать, что его нужно лучше изучить и снять с повестки. Если это сделать раз, второй и третий, то уже складывается мнение, что председательствующий не может решать вопросы.
А военным министром вместо Булганина вождь сделал маршала Василевского, многолетнего начальника Генштаба, к которому привык за годы войны.
Прирожденный штабист, Александр Михайлович Василевский стал слушателем первого набора Академии Генерального штаба (воссозданной решением ЦК и Совнаркома 2 апреля 1936 года). После окончания академии летом 1937 года полковника Василевского направили в Генштаб помощником начальника оперативного отдела. 25 августа 1941 года генерал-майор Василевский — начальник Оперативного управления и заместитель начальника Генштаба. 26 июня 1942 года генерал-полковник Василевский был утвержден начальником Генштаба.
За первые шестнадцать месяцев войны сменились три начальника Генштаба — Жуков, Шапошников, Василевский. Сталин плохо представлял себе работу Генерального штаба, недооценивал его и лишь в ходе войны убедился в ценности квалифицированных штабных работников.
С 5 июля 1942 года по 18 февраля 1945 года Василевский как представитель Ставки сорок раз выезжал на фронт. Это съело сорок процентов его служебного времени. Сталин не любил, чтобы военные засиживались в Москве, всех гонял на фронт, хотя начальнику Генерального штаба надо быть на месте.
Летом 1942 года немцы наступали, вспоминал Хрущев. Прилетел Василевский — разбираться. Больше всего нажим противника ощущала 38-я армия, которой командовал будущий маршал Кирилл Семенович Москаленко. Хрущев и Василевский поехали к нему и застали неорганизованное бегство. Стали искать командующего.
«Знали, где он находился раньше, и направились сначала туда. Когда подъехали, то там уже снимались с места кухня и военторг. Навстречу попался здоровый такой парень, лицо у него — кровь с молоком. Солдаты о таких говорили: “По физиономии видно, что из военторга”. Не выходя из машины, Василевский подозвал его. У него был мягкий характер и деликатное обращение с людьми. Он говорит:
— Послушайте, товарищ! Это не Москаленко ли хозяйство?
— Да, Москаленко.
— А где сам Москаленко?
Солдат сказал, что в таком-то селе, неподалеку отсюда, не дальше чем в десяти километрах. Мы отправились туда.
Вдруг этот солдат закричал:
— Стой! Стой!
Остановились. Этот краснорожий нахал, глядя на Василевского, говорит ему:
— Товарищ генерал, вы вчера у меня пообедали и не заплатили за обед.
Василевский перевел взор на меня, потом на него:
— Послушайте, батенька, что вы говорите? Как это могло случиться? Я же здесь не был, только что приехал.
И обращается ко мне вроде бы за подтверждением:
— Вы же знаете, что я только что приехал?
Тот нахал тут же отвернулся и ушел. Это, видно, тренированный был рвач: позволил себе обратиться к незнакомому генералу с заявлением, что тот ему не заплатил за обед. А Василевский стал оправдываться. Другой бы генерал иначе реагировал…»
Василевский, несколько полноватый, но подтянутый, мягкий и добрый, был исключительно вежлив и даже предупредителен в разговоре.
Герой Советского Союза генерал-полковник Иван Ильич Людников рассказывал «Красной звезде»:
— Жуков, как говорится, полководец от бога. Василевский, окончивший духовную семинарию, тоже обязан ставить господу богу свечку за природный полководческий талант. И хотя Жуков с Василевским были большими боевыми друзьями, а впоследствии даже породнились (старший сын Василевского Юра женился на дочери Жукова Эре), все же природа более щедро, на мой взгляд, одарила Александра Михайловича. Я имею в виду душевные качества маршала Василевского. Они сполна были даны ему от рождения, а потом «шлифовались» в духовной семинарии. Получился полководец-гуманист, с которым приятно было иметь дело…
Василевского уважали в войсках.