Говоря в целом, ситуация на Украине была тяжелейшей. Однако об этом едва ли следовало докладывать Сталину — не говоря уже о том, что сам Хрущев, по-видимому, не в полной мере понимал, с чем столкнулся. В январе 1944 года, объехав несколько освобожденных областей, он доложил Сталину, что настроение народа «очень хорошее, советское» и что он не обнаружил «никаких признаков больших [националистических] формирований». Три месяца спустя он писал Сталину, что «разговоры о действиях украино-германских националистических банд сильно преувеличены» и что, хотя руководители ОУН используют тактику запугивания, «у нас теперь есть все возможности для разгрома бандеровско-бульбовских банд». К ноябрю 1944 года настроение у повстанцев было, если верить Хрущеву, «подавленное» и многие из партизанских отрядов находились «на грани исчезновения». В январе 1945 года Политбюро ЦК КП(б)У приняло решение «использовать зимние месяцы для завершения [их] разгрома и ликвидации». В феврале была назначена и дата «полной ликвидации» националистических банд: 15 марта 1945 года 40.
В действительности украинские партизаны не были побеждены до начала 1950-х годов 41. К приходу Советской Армии едва ли не в каждом крестьянском доме был оборудован схрон с оружием, боеприпасами, запасом еды и одежды: в 1945–1946 годах советские Вооруженные силы доложили об обнаружении 28 тысяч 969 таких тайных складов. В 1944–1945-м националисты перешли от открытых позиционных боев к тактике партизанской войны и, благодаря этому, заняли довольно устойчивую позицию. В феврале 1947 года «остатки» партизанских сил составляли около 70 тысяч человек, не считая еще 63 тысяч ополченцев, организованных в особые части 42.
Борьба велась жестоко с обеих сторон. По советским данным, подпольщики-националисты совершили 14 тысяч 500 вредительских и террористических актов, уничтожили более 30 тысяч советских должностных лиц и местных жителей 43. Инструкции ОУН приказывали «ликвидировать двойных агентов (а также членов их семей, как взрослых, так и детей) всеми доступными методами — расстрел, повешение, четвертование с запиской на груди: „За сотрудничество с НКВД“». В одном только 1944-м зафиксировано множество случаев, когда бандиты снимали с убитых одежду, перебивали им руки и ноги, уродовали лица, выкалывали глаза, кастрировали и обезглавливали 44.
В период с февраля 1944-го по май 1946-го Советская Армия и НКВД уничтожили 110 тысяч 825 партизан и еще 250 тысяч 676 арестовали. Всего с 1944 по 1952 год на Западной Украине было арестовано не менее 600 тысяч человек, треть из них расстреляна, остальные две трети отправлены в лагеря или ссылку 45. Существовали и законспирированные «спецгруппы», выдающие себя за националистов. В одном случае группа фальшивых «националистов» спровоцировала крестьянскую семью на выражение националистических симпатий, а затем арестовала за «сотрудничество с бандитами». Известны случаи, когда спецгруппы совершали жестокие преступления, выдавая их за работу националистов и стремясь тем самым отвратить от партизан местное население 46.
Не доверяя западноукраинцам, советская власть присылала на партийные и силовые должности в Западном крае коммунистов из других районов страны. Положение этих людей было нелегким: с одной стороны, правительство давило на них, требуя «успехов», с другой — их жизни угрожали партизаны. Многие из них фальсифицировали работу по ловле «шпионов» и уничтожению «бандитов», искали успокоения в алкоголе, переживали нервные срывы 47. От Хрущева, в сущности, требовалось только надзирать за работой органов безопасности; однако благодаря своему стилю руководства он скоро начал принимать в борьбе с националистами активное и порой жестокое участие. В письме Сталину от 1944 года он предлагает, чтобы партизан после публичных Судов «приговаривали к смерти» трибуналы НКВД, «причем не расстреливали, а вешали». Он предлагает также создавать из руководителей областей «тройки» с правом выносить смертные приговоры и «приводить их в исполнение немедленно» 48.