Наведені вище ідейно-програмові засади були також платформою для переговорів із поляками як в еміграції, так і на теренах Закерзоння. Перші з них тривали в Римі за участі представників Закордонного представництва Української головної визвольної ради та польського лондонського еміграційного уряду до 1946 р., проте завершилися практично безрезультатно. Натомість значно продуктивнішими були переговори, які велися безпосередньо на території дії обох підпільних рухів на Закерзонні.
Навіть у цих перемовинах легко помітити несиметричність ставлення до них обох сторін. Протягом 1945―1946 рр. відбулося багато двосторонніх зустрічей між обома підпіллями, при цьому з українського боку учасниками були уповноважені найвищим керівництвом командири повстанських відділів чи очільники визвольного руху, а з польського боку переговори вели на свій страх і ризик окремі місцеві командири. Одним із них був Мар’ян Голембйовський, який всіляко намагався налагодити контакти з УПА. Коли навесні 1945 р. це нарешті вдалося і він доповів своєму вищому командиру Яну Мазуркевичу, той тільки легковажно махнув рукою і сказав: «З хамами немає про що говорити».
11 липня 1945 р. відбулася зустріч між представниками Перемиського окружного проводу ОУН та керівниками АК цієї території. Ішлося про співпрацю на локальному рівні, метою якої було не допустити непотрібного протистояння. Українські повстанці передали затриманого ними під час грабунку в українському селі поручника АК «Зигмунта» для суду над ним польськими підпільниками. Серед питань, які обговорювали, ― боротьба із кримінальними групами. Українські повстанці запевнили, що вони повністю контролюють поведінку українського населення і не допустять жодних самовільних антипольських виступів. Натомість представник польської делегації визнав, що командування АК значно гірше контролює терен і може відповідати лише за своїх вояків. «Слід зазначити, ― повідомив польський делегат, ― що останнім часом створилися групи, які діють на власний розсуд. До таких відноситься група «Яструба» (Слєпого), що здійснює грабежі і терористичні акти в цьому районі проти українського населення і яку АК збирається ліквідувати».
Незважаючи на взаємовигідні контакти і співпрацю на локальному рівні, у листопаді 1945 р. командування АК видало наказ про категоричну заборону переговорів з УПА. Однак Голембйовський порушив його і продовжував підтримувати зв’язки з українцями. Повстанські командири з обох сторін домовилися про взаємний обмін інформацією та узгодження дій. Польські підпільники навіть організували зустріч представників українського підпілля з англійським кореспондентом, який контактував із ними.
Урешті справа дійшла й до спільних українсько-польських бойових акцій. Однією з найвідоміших спільних операцій став штурм Грубешева об’єднаними силами УПА та польського підпільного формування ВіН, що прийшло на заміну АК. Зважаючи на важливість цього бою, розповімо дещо детальніше, тим паче що маємо кілька докладних звітів про його перебіг.
Уперше ідею збройної співпраці втілено в життя 6 квітня 1946 р. ― тоді підпільники УПА і ВіН провели успішну акцію на станцію Вербковичі. Це місце використовували для депортації українців. Завдяки розвідці ВіН вояки УПА отримали паролі, які допомогли їм підсунутися впритул до гарнізону Війська Польського й атакувати.
Незабаром виникла потреба провести масштабнішу наступальну операцію на містечко Грубешів. Вона мала як конкретні практичні завдання ― залякати комуністичні каральні органи, звільнити заарештованих, захопити документацію влади, так і політичні ― маніфестація спільної боротьби українців та поляків. Ідея штурму Грубешева належала полякам, її ретельно обговорили на черговій зустрічі між УПА та ВіН 18 травня 1946 р. Тоді ж визначили дату наступу ― ніч із 27 на 28 травня.
Грубешів ― типове для цього регіону провінційне містечко, більшість будинків дерев’яні, лише кілька в центрі муровані. Місто було перетворено на важливий центр нової влади: тут було розташовано повітові управління безпеки, міліції, комуністичної партії, гарнізон НКВД (близько 220 солдатів) та штаб-квартиру переселенчої комісії, яка організовувала виселення українців в УРСР. Неподалік за містом стояли вояки 5-го піхотного полку ВП та 32-го відтинка військ прикордонної сторожі. Отже, ворожі сили були досить значні, хоча польські підпільники обіцяли, що вояки ВП та прикордонники не візьмуть участі в бою.