Но главным своим партнером в осуществлении восточного проекта Пилсудский, несомненно, считал Петлюру, который после поражения от Красной армии укрылся в Польше с остатками своих войск и правительством УНР.
У Пилсудского было две возможности нанесения главного удара по Красной армии. Одна в Белоруссии, в направлении так называемых Смоленских ворот – в случае успеха отсюда можно было создать непосредственную угрозу Москве. Но у этого плана не было достаточной политической составляющей. Попытки создать в Белоруссии влиятельное движение сторонников союза с Польшей дали незначительные результаты. Основная часть белорусов отнеслась к ним безразлично или враждебно, а непримиримая позиция Ковно не оставляла надежд на осуществление проекта Великого княжества Литовского. К тому же здесь, на Западном фронте, были сосредоточены крупные силы Красной армии и сюда же перебрасывались войска, высвобождавшиеся на других фронтах Гражданской войны. С января по конец апреля 1920 года численность советских войск возросла на всем протяжении польского фронта в пять раз, до 20 дивизий и пяти бригад, и большинство этих войск было сосредоточено в Белоруссии.
Иное дело Правобережная Украина. Пилсудский был убежден (или пытался сам себя убедить) в том, что, в отличие от московского направления, на котором Красная армия использует тактику М. И. Кутузова, то есть уклонения от активных боев и отступления, вплоть до сдачи Москвы, Киев является «невралгическим пунктом» большевиков, их «болезненным местом», где они не позволят себе такой тактики. К тому же на Украине у Польши был реальный партнер – Петлюра. Правда, основную задачу по разгрому советских войск и воссозданию Украинской Народной Республики решала бы польская армия. Но рядом с ней действовали бы три украинские дивизии, и их число можно было быстро увеличить за счет добровольцев и мобилизованных. Поляки должны были оставаться на Украине до того момента, пока правительство УНР не окрепло бы настолько, чтобы самому контролировать ситуацию. Естественно, что Варшава не собиралась безвозмездно оказывать эту услугу, стоящую больших денег и жизней ее солдат. Платой за нее должны были стать территориальные уступки и экономические преференции польской стороне.
В конце 1919-го – начале 1920 года в руководстве УНР не было единства по вопросу о том, на кого опираться, чтобы вернуться в Киев. Петлюра был за союз с Польшей, а украинский премьер Исаак Мазепа допускал возможность компромисса с Россией. Но позиции Петлюры были сильнее, поэтому победила его концепция. Первые контакты Пилсудского и Петлюры датируются маем 1919 года. 2 декабря делегаты Петлюры, который еще контролировал часть украинской территории, согласились на польско-украинскую границу по линии рек Збруч и Горынь. Спустя несколько дней в Варшаве произошла многочасовая личная встреча Пилсудского с Петлюрой, в ходе которой были, видимо, обсуждены основные моменты польско-украинского взаимодействия. Вскоре в польских лагерях для военнопленных и интернированных в Брест-Литовске, Щиперно и других местах стали формироваться украинские регулярные части.
Наконец, с начала апреля 1920 года на уровне правительств начались разработка и согласование польско-украинского политического и военного договоров. 21 апреля в Варшаве в присутствии Пилсудского дипломатами сторон был официально подписан политический договор, состоявший из девяти статей. В нем констатировалось, что Польша без каких-либо предварительных условий признает независимость Украины, определялась общая граница, гарантировались национальные и культурные права своих граждан соответственно украинской и польской национальности, фиксировалось намерение заключить торгово-экономическое соглашение и военную конвенцию, а также говорилось о необходимости найти приемлемое решение проблемы крупного польского землевладения в УНР. Вслед за этим была подписана военная конвенция, передававшая украинские войска на период наступления в подчинение польскому командованию, а также регулировавшая вопросы пребывания польской армии на Правобережной Украине.
