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