В соответствии с решением Политбюро, 1931-32 гг. Евдокимов провел в Средней Азии. «Это назначение я рассматривал как незаслуженное наказание» вспоминал Евдокимов. Опала была, видимо, серьезным психологическим испытанием для Евдокимова. Некоторые из его сторонников отвернулись от своего патрона. Евдокимов рассказывал на следствии, что «в 1931 году при моей переброске в Среднюю Азию, Вейншток лично, по указанию Ягоды, выселял мою семью из квартиры, и у нас с ним после этого личного контакта не было» Другие сохранили верность — во время командировки его сопровождали Попашенко и Кальнинг.
Операции в Средней Азии принесли Евдокимову еще два ордена Боевого Красного Знамени — Таджикской и Туркменской ССР. В 1932 г. Евдокимова возвращают на Северный Кавказ. Первое путешествие в Москву закончилось неудачей — он поднялся довольно высоко, но не смог повалить Ягоду. Видимо, он вынес из этих трех лет большой опыт: неприязнь к Сталину, недоверие к политике партии и веру в силу органов, которые «могут все».
Так или иначе, в 1933 году Евдокимов снова встретился с Фриновским. Последнего назначили на высокий пост — начальника ГУПВО (Главного управления пограничных и внутренних войск). «Вскоре после назначения меня начальником ГУПВО
ОГПУ и приезда в Москву, я встретился с Евдокимовым у него на квартире. Он приехал из Ростова. Вроде бы сомнения в политике Сталина у Евдокимова сохранились: «Подожди, колхозы-то начали существовать, но это только начало, а что будет дальше — неизвестно… Дальше Евдокимов спросил: «Ты ГУПВО принял или нет?» После моего утвердительного ответа он сказал: «Тебе надо было бы заинтересоваться как следует вопросами войск. Войска будут играть большую роль в случае каких-либо осложнений внутри страны, и ты должен прибрать войска к своим рукам». Здесь, мне кажется, уместно вспомнить мысли Евдокимова 1927 года о том, что войска будут нужны в условиях возможного политического кризиса, что и произошло весной 1937 года.
Со своей стороны Ефим Григорьевич продолжал сплачивать вокруг себя кадры чекистов. В 1934 году «он говорил о том, что он имеет ряд людей внутри аппарата ГПУ, и назвал Рудя, Дагина, Раева, Курского, Дементьева, Горбача и других». Кроме того, он активно наращивал свой политический вес. В 1934 году Евдокимов был переведен на партийную работу, став первым секретарем Северо-Кавказского края, а также был избран в ЦК. Руководителем ОГПУ края стал его заместитель Дагин. Евдокимов стал сразу делать попытки протолкнуть своего помощника в Москву: «В этот же его приезд Евдокимов говорил: нельзя ли как-нибудь, через Ягоду, протянуть Дагина на оперативный отдел».