Именно по возвращении из Мельбурна его сослали. В личном деле Митрохина появились роковые слова, которые положили конец всем его надеждам: «Непригоден к оперативной работе». Позже поползли слухи, будто он не просто провалил задание, а кого-то убил. Но правда была куда более прозаичной. Он не справлялся. Он плохо проявил себя в оперативной работе в Израиле и Австралии. Но главное — он просто не вписывался в систему. «Хмурый», «молчаливый» — так позже вспоминали его коллеги по КГБ, — человек, с которым было трудно ладить. Ему не хватало навыков общения. Светское общение на дипломатических приемах давалось ему с трудом, да и обычную беседу с коллегами он поддержать не мог. За ним начала закрепляться репутация спорщика.

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

И вот в конце 1956 года руководство приняло судьбоносное решение, последствий которого никто не мог предвидеть. Его следовало перевести. Ему нравилось работать с документами. Так почему бы не отправить его в архив? В конце концов, какой вред он мог там причинить?

Эта новость стала для Митрохина потрясением. Невозможно было скрыть, что это явный признак провала, унижение. Он-то мнил себя птицей высокого полета, а теперь его отправляли под землю. В архив ссылали тех, у кого были проблемы с выпивкой или кто скомпрометировал своего начальника — туда, где о них можно было благополучно забыть.

«Я полагал, начальство решило, что я исчерпал свой потенциал на оперативной работе, и поэтому меня перевели с оперативной службы в архив. Для меня это было крайне болезненным переживанием», — вспоминал он позже.

Первое главное управление считалось элитой — счастливчиками, которым доводилось повидать мир. Служба на Западе была тем, о чем Митрохин мечтал и что рассчитывал когда-нибудь получить. Теперь же все, что ему предстояло видеть, — это стены архива и поступающие из других отделов и региональных управлений запросы о содержании бесконечных папок. Но, как позже размышлял сам Митрохин, в России говорят: не знаешь, где найдешь, а где потеряешь. Или, как выражаются на Западе, нет худа без добра. «Потому что именно работа в архиве открыла мне глаза и позволила увидеть правду».