«Микоян говорил страстно, быстро, наполовину глотая слова, как будто он боялся, что у него не хватит времени сказать все, что он хочет. Было очень трудно следить за его речью. Но даже немногих фраз в начале речи было достаточно, чтобы захватить общее внимание. Царило абсолютное молчание. Имя Сталина было упомянуто в его речи только один раз. Но критические замечания по адресу умершего вождя были почти свирепы в их категорической определенности. В предшествовавших речах не было ничего подобного этому решительному осуждению. Когда он кончил говорить, зал был охвачен возбуждением. Делегаты громко обменивались мнениями. Следующего оратора никто не слушал» (Цит. по газете «Русская мысль» (Париж). 1976. 5 февр.).
После XX съезда именно Микоян руководил формированием примерно ста комиссий, которые должны были выехать во все лагеря и места заключения СССР, чтобы быстро осуществить пересмотр обвинений политических заключенных. Прокуратура СССР, которая до сих пор медленно занималась реабилитацией, вначале возражала против создания таких комиссий, наделенных правами реабилитации и помилования. Но после вмешательства Микояна Генеральный прокурор СССР Р. А. Руденко уступил. Однако тот же Микоян в своих выступлениях перед общественностью настойчиво призывал к соблюдению осторожности и умеренности в критике Сталина. Когда на собрании московской интеллигенции некоторые писатели горячо и убедительно требовали расширения и углубления критики культа личности, Микоян не сдержался и крикнул одному из ораторов: «Вы хотите раскачать стихию?!» (См.: Свирский Г. На лобном месте. Лондон, 1979. С. 136)
В октябре 1956 года во время политического кризиса в Польше Микоян первым прибыл в Варшаву для оценки его масштабов и характера. В начале ноября, в дни восстания в Будапеште, Микоян вместе с Сусловым и Жуковым принимал решения, которые привели к его подавлению и формированию новых органов партийного и государственного руководства Венгрии.
Известно, что Микоян был дружен с Б. П. Шеболдаевым, сменившим его как партийный лидер Северного Кавказа. В 1937 году Шеболдаев был расстрелян, и Микоян молча воспринял это известие. Но в 1956 году после реабилитации Шеболдаева Микоян пригласил к себе сына погибшего друга и долго говорил ему о том, каким хорошим человеком и большевиком был его отец, с которым они вместе работали еще в Бакинской коммуне 1918 года.
Светлана Аллилуева в своей книге «Только один год» рассказывает, что уже после XX съезда КПСС она была приглашена в гости к Микояну и тот подарил ей красивый медальон с портретом Сталина.
От июньского Пленума до XXII съезда КПСС
На июньском (1957 года) Пленуме ЦК КПСС, так же как и на предшествовавшем ему заседании Президиума ЦК, Микоян твердо стоял на стороне Н. С. Хрущева. Только на Пленуме он выступал дважды и говорил каждый раз больше часа. В сущности, из членов сталинского Политбюро Микоян оказался единственным человеком, который поддержал Хрущева. После июньского Пленума Анастас Иванович входил в число трех-четырех наиболее влиятельных людей в партии и государстве. Он часто выполнял ответственные дипломатические поручения, совершая официальные и неофициальные поездки в Индию, Пакистан, Китай и некоторые другие страны. В январе 1959 года Микоян прибыл в США, чтобы открыть советскую выставку и провести переговоры о возможном визите Н. С. Хрущева в Америку. Он часто и успешно выступал в различных аудиториях в США, и ему даже задали в шутку вопрос: не собирается ли он выставить свою кандидатуру в сенат? Не слишком успешной была лишь встреча Микояна с руководством американских профсоюзов, где его встретили не особенно дружелюбно и почти загнали в угол вопросами. В конце встречи Микоян с удивлением заметил: «Руководители американских профсоюзов относятся к Советскому Союзу более враждебно, чем американские капиталисты, с которыми я встречался» (Цит. по: New Lider. 1959. 3 feb.).