Микоян воздержался, однако, от развернувшейся сразу после смерти Сталина борьбы за власть. Готовясь к аресту Берия, Хрущев посвятил в свой план Микояна в последний момент, уже перед заседанием Президиума ЦК. Но Микоян занял осторожную позицию и не спешил присоединиться к сговору. Позиция Микояна очень беспокоила Хрущева, и он поделился своими опасениями с Маленковым. Но отступать было нельзя, и они открыли заседание Президиума ЦК. Первым выступил Хрущев, подробно обосновал вопрос о необходимости отстранения Берия и выражения ему политического недоверия. После Хрущева выступил Булганин, потребовав удаления Берия из руководства. Все остальные участники заседания также поддержали Хрущева. Иначе выступил Микоян, Он согласился со многими обвинениями в адрес Берия, но тут же добавил, что Берия "учтет эту критику, что Берия не безнадежный человек, что в коллективе Берия может работать и что он может быть полезным".

После устранения Берия Микоян по всем основным вопросам поддерживал Хрущева. Он помог реабилитации и возвращению многих своих прежних друзей и сотрудников, некоторые из которых заняли ответственные посты в партийном и государственном аппарате. Он нередко встречался с родными тех своих прежних товарищей, которые были расстреляны, В 1954 году Микоян совершил поездку в Югославию, чтобы подготовить визит в эту страну советской партийно-правительственной делегации и соглашение о примирении.

Незадолго до XX съезда КПСС Хрущев предложил обсудить на съезде вопрос о преступлениях Сталина. Почти все члены Президиума ЦК были против. Микоян не поддержал Хрущева, но и не выступил против. Однако Хрущев вернулся к этому вопросу уже во время работы самого съезда. Он заявил, что обратится за решением к делегатам съезда. После трудных дискуссий с членами Президиума было решено, что Хрущев сделает доклад о Сталине на последнем заседании съезда, уже после выборов ЦК. Но еще раньше, за десять дней до того, как Хрущев прочитал свой знаменитый секретный доклад, именно Микоян неожиданно, но вполне определенно и остро поставил вопрос о злоупотреблении властью Сталина. "В течение примерно 20 лет, - сказал Микоян, - у нас фактически не было коллективного руководства, процветал культ личности", Микоян подверг критике многие ошибки Сталина во внешней политике и заявил, что "Краткий курс истории ВКП(б)" неудовлетворительно освещает историю партии и что много ошибок имеется в последней работе Сталина "Экономические проблемы социализма в СССР". Микоян не только сказал несколько теплых слов в адрес Косиора и Антонова-Овсеенко, репрессированных и погибших в конце 30-х годов, но и в более общей форме заявил, что в СССР "нет еще настоящих марксистских трудов по истории гражданской войны и что многие партийные деятели времен гражданской войны были неправильно объявлены "врагами народа" и "вредителями", Большая речь Микояна сразу стала центральным событием съезда и вызвала оживленные комментарии международной прессы.

В своей книге "Великий поворот" бывший корреспондент итальянской коммунистической газеты "Унита" Дж. Боффа так описывал выступление Микояна:

"Микоян говорил страстно, быстро, наполовину глотая слова, как будто он боялся, что у него не хватит времени сказать все, что он хочет. Было очень трудно следить за его речью. Но даже немногих фраз в начале речи было достаточно, чтобы захватить общее внимание. Царило абсолютное молчание. Имя Сталина было упомянуто в его речи только один раз. Но критические замечания по адресу умершего вождя были почти свирепы в их категорической определенности. В предшествовавших речах не было ничего подобного этому решительному осуждению. Когда он кончил говорить, зал был охвачен возбуждением. Делегаты громко обменивались мнениями. Следующего оратора никто не слушал".

После XX съезда именно Микоян руководил формированием примерно ста комиссий, которые должны были выехать во все лагеря и места заключения СССР, чтобы быстро осуществить пересмотр обвинений политических заключенных. Прокуратура СССР, которая до сих пор медленно занималась проведением реабилитаций, вначале возражала против создания таких комиссий, наделенных правами реабилитации и помилования. Но после вмешательства Микояна Генеральный прокурор СССР Р, А. Руденко уступил. Однако тот же Микоян в своих выступлениях перед общественностью настойчиво призывал к соблюдению осторожности и умеренности в критике Сталина. Когда на собрании московской интеллигенции некоторые писатели горячо и убедительно требовали расширения и углубления критики культа личности, Микоян не сдержался и крикнул одному из ораторов: "Вы хотите раскачать стихию?!"

В октябре 1956 года во время политического кризиса в Польше Микоян первым прибыл в Варшаву для оценки его масштабов и характера. В начале ноября в дни восстания в Будапеште Микоян вместе с Сусловым и Жуковым принимал решения, которые привели к его подавлению и формированию новых органов партийного и государственного руководства Венгрии.

Известно, что Микоян был дружен с В. Шеболдаевым, который сменил его как партийный лидер Северного Кавказа. В 1928 году Шеболдаев был расстрелян, и Микоян молча воспринял это известие. Но в 1956 году после реабилитации Шеболдаева Микоян пригласил к себе сына своего погибшего друга и долго рассказывал ему о том, каким хорошим человеком и большевиком был его отец, с которым они вместе работали еще в Бакинской коммуне 1918 года.