«В конце 1921 года по инициативе ЦК партии с группой работников Гомельской ЧК я был направлен в Башкирию и выполнял там обязанности заместителя председателя ЧК автономной республики. Нас послали туда в связи с тем, что в Башкирии не все шло гладко с созданием местного государственного аппарата, возникали разногласия на почве межнациональных отношений. По приезде в Уфу мы, изучив обстановку, в корне изменили направление деятельности Башкирской ЧК, пресекли высокомерие, элементы великодержавного шовинизма, имевшие место в коллективе местных чекистов, ввели в аппарат ЧК национальные кадры, установили деловые отношения с ЦИК и Совнаркомом Башкирии. В короткий срок нам удалось нормализовать ситуацию и создать необходимые условия для становления и развития этой республики».
За этими сдержанными, дипломатическими фразами (Алексеев вспоминал о своей молодости, успев побывать уже дипломатом… и разведчиком) видно, каким непростым было положение в Башкирии в начале 20-х.
А кроме борьбы с бандитизмом и национал-сепаратизмом приходилось заниматься и контрразведывательной работой. В Башкирии действовал филиал известной американской организации помощи голодающим «АРА», среди сотрудников которой были и сотрудники спецслужб, в частности, уполномоченный в Уфе Крейг.
Москва, работа на Лубянке, в Восточном отделе и учеба в военной академии
В мае 1923 года Эйтингона и Алексеева вызывают в Москву и направляют на работу в Восточный отдел Секретно-оперативного управления ОГПУ. Николай Львович Волленберг, первый учитель Наума Эйтингона в чекистском ремесле, оставался в Уфе на посту начальника областного отдела ОГПУ до 1926 года, когда перешел в центральный аппарат. В дальнейшем он также, как и его ученики Эйтингон и Алексеев, работал в разведке. Но их служебная география не пересекалась.
Немного о Восточном отделе. Подразделение такого типа существовало в качестве самостоятельной структурной единицы (а не в составе Иностранного отдела ОГПУ, как пишут некоторые авторы) в течение 8 лет. Идея организации специального органа для работы на Востоке обсуждалась еще в разгар Гражданской войны. 31 декабря 1919 года Политбюро ЦК РКП(б) обсудило предложение Ф. Э. Дзержинского об учреждении при Особом отделе ВЧК «специального подотдела по борьбе с контрреволюцией на Востоке». Председатель ВЧК предложил назначить руководить этим органом партийного работника, работавшего в Киргизском крае (то есть в нынешнем Казахстане), Вадима Лукашева. Политбюро рекомендовало Дзержинскому, «не создавая особого подотдела и вообще руководимого из Москвы специально аппарата борьбы с контрреволюционным движением среди мусульман, ограничиться сосредоточением в Особом отделе всех сведений, собираемых ЧК в населенных мусульманами губерниях, и дачей этим губчека общих указаний».