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