Конфликт с Н. Г. Кузнецовым возник у Хрущева еще до XX съезда КПСС. Вскоре после войны, по предложению Сталина, Политбюро одобрило решение о строительстве большого числа крупных надводных кораблей как основы советского военно-морского флота. К 1954 году оно подходило к концу, на некоторых крейсерах уже устанавливались дальнобойные орудия. Однако для завершения этой программы требовались еще многие миллиарды рублей. Но Хрущев не разделял ни военно-морских идей, ни амбиций Сталина. Стараясь найти дополнительные средства для развития экономики, он высказывался за постепенное сокращение военных расходов. Еще в 1954 году, возвращаясь из Китая, он познакомился с положением дел на Тихоокеанском флоте, и маневры крупных кораблей произвели на него скорее отрицательное, чем положительное впечатление. Хрущев полагал, что развитие ракетно-ядерного оружия делает крупные военные корабли лишь удобной мишенью для противника. Поэтому он выступал за преимущественное развитие подводного флота и небольших кораблей, оснащенных ракетным оружием. Точка зрения Хрущева возобладала, и было решено отправить недостроенные крупные корабли на переплавку. Кузнецов решительно возражал и, уходя с заседания Президиума ЦК, бросил фразу, адресованную прежде всего Хрущеву: «Флот не забудет вам этого». Не забыл флот, но не забыл инцидента и Хрущев. Не самые лучшие отношения сложились и между Кузнецовым и Жуковым. При Сталине существовал самостоятельный наркомат, а затем министерство Военно-морского флота, и Кузнецов был до 1953 года наркомом и позднее министром ВМФ СССР. Но с середины 1953 года все Вооруженные силы СССР подчинялись министру обороны СССР, и Кузнецов стал одним из его заместителей. Еще в 1955 году специальная комиссия Министерства обороны СССР проверила работу некоторых военно-морских баз и сочла ее неудовлетворительной. Ответственность за это возлагалась на Кузнецова, который в 1955 году потерял свой пост члена ЦК КПСС, а в 1956 году после гибели линкора «Новороссийск» был снят с поста главкома ВМС и лишен звания адмирала флота Советского Союза. Новым командующим Военно-морским флотом СССР стал адмирал С. Г. Горшков.
Изменения в руководстве КГБ произошли в 1958 году. Известно, что одним из требований группы Молотова – Маленкова являлось смещение И. Серова с поста председателя КГБ. Серов, конечно, знал об этом, чем, в частности, объяснялось его особенно активное поведение в июне 1957 года. Его высокое положение вызывало недовольство И. Б. Тито, который не только хорошо знал прошлое председателя КГБ, но и возлагал на него ответственность за арест и расстрел Имре Надя. Но Серов был лично предан и близок Хрущеву, и последний старался его выгородить, хотя за ним, как и за всяким крупным работником, давно работавшим в КГБ, тянулся длинный список различного рода незаконных акций. Достаточно сказать, что именно Серов руководил выселением некоторых народностей с Северного Кавказа. После XX съезда КПСС и возвращения домой миллионов реабилитированных граждан вскрывались все новые и новые преступления НКВД – МВД – МГБ, и поэтому игнорировать темное прошлое председателя КГБ становилось все труднее. Непосредственным поводом к смещению Серова, по некоторым свидетельствам, послужило дело о короне бельгийского королевского дома. Похищенная нацистами, она находилась на территории Германии, и следы ее терялись где-то в зоне советской оккупации. Но если корона венгерских королей обнаружилась в одном из музеев США, то бельгийская корона, как показало длительное следствие, находилась у И. Серова. Воспользовавшись своим положением одного из руководителей военной контрразведки СМЕРШ («смерть шпионам»), он похитил ее среди многих других ценных вещей. Без всякой огласки корона вернулась в Бельгию, а Серов потерял свой пост председателя КГБ. Но Хрущев не только отказался начать расследование всей прошлой деятельности Серова, многие годы работавшего на Украине, но назначил его начальником ГРУ – Главного разведывательного управления Советской армии, организации, работавшей в тесном контакте с КГБ. Только через несколько лет в связи с разоблачением Пеньковского, английского шпиона, занимавшего высокий пост не только в Государственном комитете по науке и технике, но и в ГРУ и имевшего доступ к важнейшим секретам Советского государства, И. Серов, покровительствовавший Пеньковскому, был снят со всех ответственных постов.