Как рассказывала дочь Малиновского Наталья Родионовна со слов товарища отца по академии имени Фрунзе генерал- майора Ивана Николаевича Буренина, во время первой встречи Жукова и Малиновского в ноябре 1929 года в Москве, когда Жуков был командирован на Курсы усовершенствования высшего начсостава при Военной академии имени Фрунзе, а Малиновский был слушателем этой академии, Георгий Константинович окликнул Родиона Яковлевича с матерщиной, а тот ответил соответствующим образом. Георгий Константинович сначала опешил от полученного отпора, а потом поздоровался с Родионом Яковлевичем вполне вежливо, по имени-отчеству и без какой- либо грубости. Жуков понял, что Малиновский хамства терпеть не будет, в случае чего и сдачи даст, а ростом он повыше, да и в плечах не уже. А уж силушки у него — дай бог каждому! Ведь в Первую мировую пулемет на своем горбу приходилось таскать! Поэтому за все время совместной службы Георгий Константинович его не то что по физиономии не бил, но даже слова матерного не сказал. Однако два маршала друг друга искренне терпеть не могли, хотя внешне это скрывали.
Управляющий делами Совета министров СССР Михаил Смиртюков вспоминал: «Как-то я заприметил, что маршалы Жуков и Малиновский повадились ловить рыбу с Рублевской плотины. Интересно то, что они никогда не рыбачили там вместе. Жуков подъезжает — Малиновский сворачивает удочки. И наоборот. Видимо, крепко не любили друг друга».
Хрущев знал, кого назначить Жукову первым заместителем. Никита Сергеевич нисколько не сомневался, что Жуков и Малиновский против него никогда не сговорятся.
21 ноября 1956 года Жуков предложил освободить от должности заместителя министра обороны маршала С.С. Бирюзова, оставив его главнокомандующим войсками ПВО страны. Мотивировалось это необходимостью сократить число заместителей министра обороны. Однако Президиум ЦК не поддержал Жукова. Сергей Семенович был человеком Хрущева и Малиновского, а не Жукова, и попытка Георгия Константиновича понизить статус Бирюзова в центральном аппарате Министерства обороны могла только еще больше насторожить Никиту Сергеевича.
Как снимали Жукова с поста министра обороны, хорошо известно. Хрущева встревожило то, что Жуков предложил заменить председателя КГБ И.А. Серова и министра внутренних дел Н.П. Дудорова на армейских генералов, а на пост министра внутренних дел выдвинуть маршала Конева. Это было похоже на подготовку военной хунты для будущего переворота. А когда во время октябрьского визита Жукова в Югославию и Албанию генерал У.Х. Мамсуров сообщил Хрущеву и Малиновскому, что он является начальником созданной без ведома ЦК партии школы диверсантов в Тамбовской области, которая должна быть полностью сформирована уже к 15 января 1958 года (официально она называлась вторым воздушно-десантным училищем в Тамбове, подчиняющимся Главному разведывательному управлению Генштаба), Хрущев понял, что Жуков создает лично преданную ему воинскую часть для возможного переворота и его пора снимать с поста министра обороны. Тем более, что будущие курсанты должны были учиться по 6–8 лет — больше, чем в училищах и академиях. Похоже, Жуков готовил собственную «преторианскую гвардию», опираясь на которую рассчитывал захватить и удерживать власть.
Когда на октябрьском пленуме ЦК снимали Жукова, Конев в последний день работы пленума, 29 октября, подал в Президиум следующую записку: «Тов. Микоян А.И. в своем выступлении назвал меня другом т. Жукова Г.К. Это не соответствует действительности. Наши отношения с т. Жуковым были только служебно-деловыми и не больше. Насчет дружбы Вам известно, Никита Сергеевич». Конев также заклеймил Жукова в выступлении на пленуме, а потом написал (или, скорее подписал) направленную против Георгия Константиновича статью в «Правде».