С генералом Марчем встречался не только Булах-Балахович, но и генерал Родзянко, передавший Марчу компромат на атамана. Но эти материалы не смутили английских генералов. Тем временем Юденич и Родзянко тайно готовили арест Балаховича и некоторых лиц из его окружения. В Псков с этой целью был направлен отряд полковника Перемыкина в составе трех полков и двух броневиков. Однако 23 августа Перемыкин обнаружил в Пскове только штаб батьки, а все его войско находилось на фронте. Балахович и несколько чинов его штаба были помещены под домашний арест, полковник Стоякин во время ареста был задушен. Части же атамана оперативно скрылись на эстонской территории. Вскоре Булахович бежал, каким-то образом сумев ввести в заблуждение охрану. Уже 25 августа «батька» с небольшим отрядом верных ему «зеленых» завязал бой против красноармейских частей. 27 августа отряд Балаховича ушел в Эстонию, переправившись на западный берег реки Великой под прикрытие 2-й эстонской дивизии. С сентября 1919-го атаман находился на службе эстонского государства, в составе 2-й дивизии.

В это время во главе небольшого автономного отряда Балахович совершал набеги на тылы красных, прикрывал часть территории Эстонии на стыке эстонской, латышской и российской границ. Конфликт между Балаховичем и Юденичем стал одной из причин разрыва армии Эстонии с Северо-Западной армией. Эстонское командование сняло с Псковского фронта свои подразделения, что привело к захвату Пскова частями Красной армии.

В середине сентября 1919 года Балахович стал участником заговора, целью которого было смещение командования Северо-Западной армии — генералов Юденича и Родзянко. Атаман должен был выехать со своим отрядом в 300 бойцов в Нарву и устранить из армии сторонников Юденича. Но путь эшелону батьки преградил эстонский бронепоезд: эстонские генералы решили не разваливать окончательно армию белых. Впрочем, вскоре Балаховичу была дана возможность собирать под свое начало в Тарту офицеров и солдат разгромленной под Петроградом в ноябре 1919-го Северо-Западной армии Юденича.

22 января 1920 года генерал Юденич объявил о роспуске своей армии. А в ночь на 29 января Булах-Балахович в сопровождении своего помощника Павловского, нескольких «партизан» и эстонских полицейских арестовал Юденича прямо в его номере гостиницы «Коммерс» в Таллинне. Этот арест Балахович объяснял необходимостью определения расчетов по активам Северо-Западной армии. Однако, когда разразился скандал, связанный с этим арестом, после вмешательства французской и английской военных миссий эстонские власти немедленно освободили генерала и издали приказ об аресте самого Балаховича. Атаман был задержан и увезен в местечко Тайс. Но вскоре туда прибыла английская миссия и освободила атамана. Скрываясь от новых врагов, Балахович бежал в Алуксне.

В феврале 1920 года Булах-Балахович при посредничестве военного атташе в Риге обратился к руководителю польского государства Юзефу Пилсудскому с просьбой принять его на службу для борьбы с большевиками. После получения согласия Балахович со своим отрядом перешел линию фронта и прибыл в Двинск, где был торжественно принят польским генералом Эдвардом Рыдз-Смиглы.

С февраля по апрель 1920 года Балахович занимал должность командующего Особой добровольческой диверсионной группой — вспомогательным отрядом, подчиненным Главному командованию польской армии и польской разведки. С этого момента он воюет на стороне Польши, совершая рейды в тылы красных, нападая на штабы, обозы, опорные пункты Красной армии в районе Восточного Полесья.

В конце апреля польская армия при поддержке частей Петлюры начала масштабное наступление по всей линии польско-советского фронта. Отряд Балаховича, который к этому времени увеличился до 800 сабель и 500 штыков, наносил удары по тылам отступающих большевиков, сея панику и дезертирство. 30 июня отряды Балаховича нанесли тяжелое поражение красным в районе Славечна. 3 июля балаховцы атаковали Веледники, захватив штаб расквартированной там бригады. К августу 1920 года вспомогательный отряд Балаховича был переформирован в Партизанскую белорусскую дивизию в составе 1-го Партизанского, 2-го Псковского, 3-го Островского, 4-го Вознесенского полков и конного полка — всего 1500 штыков и 400 сабель. С 17 августа по 7 сентября дивизия Балаховича действовала в районе Влодавы. 23 августа «балаховцы» нанесли внезапный удар по позициям красных, захватив два орудия и 250 пленных. 27 августа они выбили противника из Персепы. Партизанские рейды на первых порах приносили Балаховичу удачу...

В это же время атаман вступил в контакт с Борисом Савинковым, заручившись его поддержкой. В конце августа 1920 года между Балаховичем и Савинковым — главой Российского политического комитета было заключено соглашение, по которому Савинков обязывался поддержать кандидатуру Балаховича на пост главнокомандующего русскими вооруженными силами в Польше, а Балахович признавал политическое руководство Савинкова над его армией. В то же время атаман оговорил свою полную самостоятельность в оперативных действиях.

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

26 сентября 1920 года Партизанская Белорусская дивизия Балаховича вышла в тыл к красным и, разбив запасной полк большевиков, захватила город Пинск и штаб 4-й армии. После этого 4-я армия оказалась разделенной на две части, армейские штабисты еще долго прятались в окрестных лесах, едва унеся ноги из Пинска.

В октябре польское командование дало согласие на развертывание в своем тылу самостоятельной армии Балаховича в составе трех дивизий в 15–20 тысяч бойцов — Народно-добровольческой армии (НДА), в основу создания которой был положен партизанский принцип. НДА получила от польского командования статус «особой союзнической армии». Но сам Балахович называл себя бацькой Партизанской Зеленой крестьянской армии. В НДА входили: 2-я дивизия полковника Микоши (четыре пехотных полка, две артиллерийские батареи и инженерная рота), 3-я дивизия генерала Ярославцева (четыре полка и артиллерийская батарея), кавалерийская дивизия (четыре полка). Самостоятельными соединениями в НДА были бригада есаула Сальникова (Донской конный полк в 600 сабель и батарея), партизанский полк украинского атамана Искры, Еврейский батальон-дружина прапорщика Цейтлина и Мусульманский полк поручика Сарадина. К ноябрю 1920 года численность НДА составляла от 12 до 14 тысяч бойцов при 36 орудиях, 150 пулеметах, двух аэропланах.