Первой зарубежной поездкой в качестве министра иностранных дел для него стало ближневосточное турне в июне 1956 года. В контексте начинавшегося крушения колониальной системы и усиления международного веса и влияния афро-азиатских народов Советский Союз уделял особое внимание перспективам налаживания отношений с арабскими странами, которые активно проявляли себя в формировавшемся движении неприсоединения. Шепилов твердо проводил линию на завязывание дружеских и партнерских связей со странами Ближнего Востока, особенно теми из них, кто настойчиво выступал за упрочение своего суверенитета и независимости. Он всячески подчеркивал, что на этом пути арабские страны найдут в лице СССР надежного союзника. В ходе бесед и переговоров им был предпринят зондаж по поводу возможности заключения двусторонних договоров о дружбе и сотрудничестве. Однако было очевидно, что на том историческом этапе арабские государства еще опасались "чрезмерного сближения с Москвой".
В Каире Шепилов провел переговоры с египетским лидером Гамалем Абдель Насером. Основное внимание было уделено вопросам налаживания практического партнерства в контексте предпринимавшихся правительством Египта усилий по упрочению экономической независимости государства. Шепилов, руководствуясь переговорными инструкциями, ясно дал понять египетскому руководству, что СССР мог бы оказать содействие в строительстве Асуанской плотины, строительстве металлургического комбината, создании машиностроительной отрасли. Он акцентировал внимание на важности разработки перспективного плана экономического развития Египта, при этом египтяне попросили срочно прислать "двух экономистов-плановиков для оказания содействия". Кроме того, была высказана просьба к Шепилову как одному из авторов "о высылке трех экземпляров политэкономии социализма на английском языке".
16 июля 1956 г. Шепилов выступил с заявлением в Верховном Совете СССР о позиции Советского правительства в вопросе прекращения испытаний ядерного оружия. Он также затронул и вопросы сокращения вооруженных сил и вооружений обычного типа. "Советский Союз последовательно добивается того, чтобы проблема разоружения была сдвинута с места и поставлена на практические рельсы. Неопровержимым тому свидетельством служат не только предложения о существенном сокращении вооруженных сил и вооружений, а также о запрещении атомного оружия, но и проводимые СССР в одностороннем порядке мероприятия по значительному сокращению своих вооруженных сил и вооружений".
Месяц спустя после поездки по арабским странам Шепилов вновь вынужден был сфокусировать внимание на ближневосточной проблематике. 26 июля 1956 г. в Каире был принят декрет о национализации Суэцкого канала. Великобритания и Франция предприняли экономические санкции и начали военные приготовления с целью оказания нажима на Египет. В заявлении правительства СССР от 9 августа, подготовленном при участии Шепилова, содержалось осуждение действий западных держав против Египта, которые квалифицировались как угроза миру и безопасности.
Шепилов возглавил делегацию СССР на Лондонской конференции по вопросу о Суэцком канале, проходившей 16-23 августа. На ней он выступил за мирное решение суэцкой проблемы "на основе сочетания национальных интересов Египта и интересов обеспечения свободы судоходства" по каналу. 23 августа министр заявил, что единственным путем решения вопроса о Суэцком канале, отвечающим современным условиям, является признание суверенитета Египта как независимого и полноправного государства, полного хозяина Суэцкого канала. Но 30 октября начались военные действия против Египта. Советское правительство осудило агрессию и потребовало, чтобы Совет Безопасности принял меры к прекращению агрессии против Египта.
Шепилов способствовал нормализации советско-японских отношений, выступал за установление с Токио политического диалога. В беседах с министром иностранных дел Японии в Москве и Лондоне в августе 1956 года он настойчиво отстаивал идею налаживания добрососедских связей, недопущения использования национальных территорий для базирования иностранных войск. Эти контакты Шепилова способствовали подготовке визита в Москву в октябре премьер-министра Японии Хатоямы, в переговорах с которым он принял деятельное участие. Результатом большой дипломатической работы явилось подписание Совместной декларации, провозгласившей прекращение состояния войны и восстановление мира и добрососедских отношений со дня вступления в силу этого документа. СССР отказывался от всех репарационных претензий к Японии. Была достигнута договоренность об обмене дипломатическими представителями в ранге посла. Помимо этого был подписан протокол о развитии торговли и взаимном предоставлении режима наиболее благоприятствуемой нации.