29 декабря 1921 года Николай Волленберг был назначен председателем Башкирской ЧК и выехал в Стерлитамак, являвшийся в то время столицей автономной республики. 6 июля 1922 года он был утвержден начальником Башкирского областного ГПУ.

В конце 1921 года в Башкирии возникла критическая ситуация. В республике сложились ненормальные отношения между местной ЧК и национальным башкирским руководством. Несмотря на то, что в Башкирии уже была установлена советская власть, некоторые местные советские работники, не разобравшись в обстановке, а иногда и отдавая дань пережиткам прошлого, проявляли открытое недоверие к башкирским руководителям. Ответной реакцией стали вспышки буржуазного национализма среди башкир. Обострилась национальная рознь между башкирами и татарами. Тяжело сказались на настроениях людей неурожай и голод.

Не все гладко шло в Башкирии и с созданием местного государственного аппарата, регулярно возникали разногласия на почве межнациональных отношений.

Положение в республике усугублялось еще и тем, что башкирское население оставалось крайне недовольно проведенной до революции столыпинской аграрной реформой, в результате которой переселенцы из Центральной России получили лучшие земельные наделы. Этим обстоятельством воспользовались башкирские националисты, которые выдвинули лозунг: «Всю землю Башкирии — только башкирам». Таким требованием в свою очередь были недовольны татары, являвшиеся более развитыми в экономическом отношении.

Лидером башкирских националистов стал 27-летний сын сельского муллы, получивший хорошее образование, Ахмет-Заки Валидов. В марте 1919 года была создана Башкирская автономная республика в составе РСФСР, столицей которой до июня 1922 года был город Стерлитамак. Валидов возглавил Башкирский ревком и вскоре вступил в РКП(б). Именно при нем начались гонения на лиц татарской и русской национальностей. Ситуация осложнилась еще и тем, что в 1920 году в Белебеевском, Бирском и Мензелинском уездах Башкирии вспыхнуло крестьянское восстание, получившее название «Черный орел» и проходившее под оригинальным лозунгом: «Долой коммунистов, да здравствуют большевики и свободная торговля».

В целях исправления создавшегося положения ЦК РКП(б) принял решение сменить руководство ЧК автономной республики. В помощь Волленбергу, назначенному руководителем местной ЧК, были направлены два его сотрудника по Гомельской губернской ЧК: Алексеев-Железняков был назначен заместителем председателя Башкирской ЧК, а Эйтингон — членом коллегии.

В короткий срок Волленбергу и присланным ему в помощь чекистам удалось нормализовать обстановку в республике и создать необходимые условия для ее развития. Они в корне изменили направление деятельности Башкирской ЧК, пресекли высокомерие, элементы великодержавного шовинизма, имевшие место в коллективе местных чекистов, ввели в аппарат ЧК национальные кадры, установили деловые отношения с ЦИК и Совнаркомом Башкирии.

Приходилось чекистам бороться и с бандитизмом, который в годы Гражданской войны в России расцвел махровым цветом по всем городам и весям обширного государства. В Башкирии также активно действовал филиал американской организации по оказанию помощи голодающим Поволжья «АРА», служившей «крышей» для американских разведчиков. А они в свою очередь стали объектами активного интереса со стороны чекистов Волленберга.

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

В Башкирии Волленберг проработал до 1926 года. В 1924 году «за беспощадную борьбу с контрреволюцией» он был награжден нагрудным знаком «Почетный работник ВЧК — ГПУ».

Так Николай Львович столкнулся с проблемами Востока, с которыми в дальнейшем был связан на протяжении длительного времени.