По возвращении в Советский Союз в 1936 году Андрею Макаровичу было предложено перейти на работу в Иностранный отдел, и он стал работать в секторе, руководившем разведывательной деятельностью в странах Ближнего и Среднего Востока. А в следующем году он был направлен резидентом в Тегеран.
Страну он знал достаточно хорошо и сразу включился в работу. Время было тревожное. Итальянский фашизм пробовал силу оружия в Абиссинии, шла война в Испании, испытывала прочность наших рубежей Япония, Гитлер приступил уже к реализации своих агрессивных планов в Европе.
Главная опасность для нашей страны исходила со стороны Германии и Японии. Однажды Андрею Макаровичу пришлось решать задачу по внедрению в агентурную сеть японской разведки своего агента. Анализ сведений о деятельности японцев в Иране позволил ему заподозрить фирму, в которой работал инженер-японец, в принадлежности к японской разведке. Была проведена нехитрая комбинация: этого инженера познакомили с одним из проживавших в Иране выходцев из Средней Азии. Тот оказался в числе искавших работу на фирме, где «трудился» инженер-японец. Как только японцу стало ясно, что новый работник фирмы имеет отношение к советским республикам Средней Азии, «инженер» открыто заявил, что он японский разведчик, и «завербовал» агента нашей резидентуры. А дальше все развивалось по законам детективного жанра.
То ли дело было неотложное, то ли команда из Токио подталкивала, только японский разведчик начал уговаривать своего нового подопечного побыстрее отправиться в Среднюю Азию, добраться до Ашхабада, а там выйти на контакт с агентом японской разведки, который оказался без связи.
Надо ли говорить о том, что Москва одобрила план японского «инженера», помогла осуществить успешный вывод его посланца в Среднюю Азию, добраться до Ашхабада и выйти на того, кто проводил враждебную деятельность на территории Советского Союза.
Подчеркнем, что это лишь один небольшой эпизод той активной разведывательной работы, которую проводил Андрей Макарович От-рощенко в Тегеране.
Очевидно, он продолжал бы и дальше плодотворно руководить работой резидентуры, если бы не срочный вызов в Москву в 1938 году и совершенно неожиданный для Отрощенко арест. Сработал клеветнический донос. Восемь месяцев следователи пытались вытянуть признание в его связях с вражескими разведками. Не добившись признания в несовершенных грехах, Андрея Макаровича освободили и направили на работу в Одессу, где он был назначен вначале начальником отделения, а затем руководителем контрразведывательного отдела областного управления.
В Одессе его застигла Великая Отечественная война. Одесские чекисты активно участвовали в героической обороне города. Андрей Макарович покинул осажденную Одессу с последним катером.
А.М. Отрощенко прибыл в Куйбышев, где размещалась часть центрального аппарата НКВД. Он попросил направить его на фронт, но руководство решило иначе. Отрощенко получил назначение на должность начальника одного из отделов центрального аппарата внешней разведки. Отдел занимался организацией разведывательной работы в странах Азии, в частности в Иране, где большую опасность представляла активность гитлеровской агентуры.
Когда было принято решение о проведении в Тегеране конференции руководителей стран — членов антигитлеровской коалиции, на советскую разведку легла ответственная задача по обеспечению безопасности совещания в верхах. Тем более что разведка получила сведения о подготовке гитлеровцами острой акции против глав делегаций.
За несколько дней до начала Тегеранской конференции из Москвы в Иран специальным поездом выехала группа руководящих работников Министерства государственной безопасности СССР. В ее состав входил и Андрей Макарович.
Спустя много лет, уже находясь на заслуженном отдыхе, Отрощенко вспоминал многие эпизоды той напряженной поры. Упомянем здесь о некоторых из них.
Поезд доставил группу чекистов до станции Астара, а далее надо было добираться до Тегерана на автомашинах, которые были доставлены тем же поездом. Андрей Макарович ехал в машине, предназначенной в Тегеране для И.В. Сталина. В дороге, уже на территории Ирана, с автомашиной что-то случилось, она стала неуправляемой. Только мастерство водителя позволило избежать аварии. Как было установлено позднее, произошла поломка в рулевом управлении. Что явилось ее причиной — осталось загадкой. Шума по этому поводу не поднималось, неисправность была устранена, и автомобиль сослужил свою службу.
В Тегеране Отрощенко с головой окунулся в деятельность по обеспечению безопасности работы конференции. Помимо усилий, направленных на нейтрализацию и срыв подрывных акций гитлеровской разведки, резидентуре пришлось заниматься и союзниками.
Были получены достоверные данные о намерении английской разведки развернуть активную агентурную работу против советских представительств в Иране. Поэтому те наши разведчики, кому довелось в ходе конференции наблюдать поведение Черчилля, с удивлением отмечали какую-то угодливость «британского льва» по отношению к И.В. Сталину.