В середине сентября 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 пулеметах, двух аэропланах.

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

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

25 октября 1920 года Балахович и Савинков со своими частями перешли демаркационную линию фронта. Штаб повстанцев обосновался в Кожан-городке, куда 2 ноября прибыл резидент английской разведки и личный друг Савинкова Сидней Рейли (С. Розенблюм). Рейли считал, что идея освобождения белорусских земель от большевиков объединит белорусов, поляков и русских, хотя полного согласия между ними не было даже в частях повстанцев.

В ноте СНК РСФСР правительству Великобритании от 28 октября 1920 года подчеркивалось, что, несмотря на перемирие, враждебные действия балаховцев в Белоруссии продолжаются. В Риге советский представитель вручил ноту протеста правительству Латвии в связи с вербовкой на ее территории в «обширных размерах» бежавших из России белогвардейских офицеров и других контрреволюционных элементов для пополнения армии Савинкова–Балаховича в Польше.