19 сентября 1939 года Меркулов и Серов уже почувствовали первый вкус оперативных проблем, с которыми им придется столкнуться при выполнении приказов Берии. Они жаловались, что им понадобится больше оперативных групп, чем они планировали создать. 28 сентября в предварительном докладе по проведенным операциям НКВД Меркулов отметил, что украинские националисты, такие как члены Организации Украинских Националистов (ОУН) превысили всех других лиц, арестованных в соответствии с критериями, установленными приказом Берии. Чтобы продемонстрировать это, Меркулов доложил, что из 1923 арестов, произведенных 1-й оперативной группой, более 1000 лиц были членами или активистами националистических организаций. Он также сообщил об «огромном количестве» обнаруженного оружия. ^[40]

Упоминание Меркуловым ОУН не должно было удивить Серова или Хрущева. Эта группа существовала в различных формах со времени падения недолговечной Украинской народной республики. Объявленное в январе 1919 года и объединившее все украинские земли, включавшие Западную Украину, или так называемую Галицию, район Карпатских гор, Буковину и Бессарабию, это недолгое независимое образование прекратило свое существование после Рижского договора 18 марта 1921 года. Советский Союз сохранил восточную и центральную части Украины как Украинскую ССР. Чехословакия получила Карпатскую Украину, Румыния оккупировала Буковину и Бессарабию, а Западная Украина была отдана Польше. В период 1920 — 30-х годов идея независимой Украины продолжала жить в Галиции, несмотря на усилия поляков подавить ее поборников. Советские органы НКВД считали ОУН серьезной угрозой, полагая, что ее руководитель полковник Евген Коновалец установил контакт с германским Абвером, встречался с Гитлером и даже получил разрешение обучать своих приверженцев в нацистской партийной школе в Лейпциге. Как писал Павел Судоплатов, ветеран НКВД, сотрудник отдела спецопераций, в 1935 году он был послан, как нелегал, за границу, чтобы установить контакт с Коновальцем и проникнуть в ОУН; два года спустя он лично докладывал об этом Сталину. В мае 1938 года Судоплатов убил Коновальца, на место которого в ОУН встал его заместитель полковник Андрей Мельник. Его полномочия оспаривал Степан Бандера, и ко времени разгрома Польши националистическое движение раскололось на два лагеря — сторонников Мельника и сторонников Бандеры, получивших название «бандеровцы». Обе стороны заявляли о своей верности принципам независимости Украины и отрицали, что служили германским интересам. ^[41]

Свидетельства о размерах украинских националистических военизированных формированиях росли. В декабре 1940 года член одной из военизированных групп, арестованный во время перехода границы, рассказал, что во Львове есть контрреволюционная повстанческая организация, насчитывающая 2000 вооруженных членов. В группе есть шесть тяжелых пулеметов; она имеет подчиненные отряды в городах Станислав (с 1962 г. — Ивано-Франковск), Коломыя, Перемышль и Тарнополь (с 1944 г. — Тернополь). К декабрю 1940 года НКВД Украинской ССР знал от своего агента «Украинца», что Львов является подпольным центром ОУН на Западной Украине. Также было известно о расколе между Бандерой и Мельником, которые оба поддерживали контакты с немцами. ^[42]Страхи, растущие в Киеве и Москве по поводу усиления ОУН, не были беспочвенными, как можно видеть из «объединенного генерального плана штаба восстания ОУН» — ответа на директивы Абвера поднять восстание на Украине для подрыва тыла Красной Армии, восстания, в котором ОУН выйдет из подполья, чтобы вести народ «во всех украинских землях, чтобы полностью разбить „Московию, Советскую тюрьму народов“». ^[43]

В середине апреля 1941 года комиссар госбезопасности Украинской ССР П. И. Мешик написал Хрущеву, что его организация пришла к выводу, что немцы будут использовать оуновцев как «пятую колонну» в своем планируемом нападении на СССР, потому что «они представляет серьезную силу, поскольку хорошо вооружены и пополняют свои запасы путем переброски оружия из Германии». ОУН не собиралась ждать до начала войны, ее отряды терроризировали председателей сельсоветов до такой степени, что даже просоветски настроенные люди боялись сообщать о них. Мешик рекомендовал предпринять конкретные действия, чтобы лишить оуновцев базы поддержки — включая смертную казнь для членов организации, нелегально живущих на территории Западной Украины, конфискацию их имущества и ссылку членов их семей. В связи с тем, что кулаки составляли важную часть структуры ОУН, их также нужно было высылать в отдаленные области, а их земли передавать колхозам. ^[44]

29 апреля Берия направил директиву комиссарам госбезопасности и внутренних дел Украинской ССР по укреплению мер для прекращения террористической активности ОУН в западных областях республики. Он сообщал об увеличении случаев террора (в апреле 1941 года их было тридцать восемь) и отмечал, что оуновцы наносят потери даже сотрудникам НКГБ и НКВД. Он подчеркивал, что на органах НКГБ лежит полная ответственность за уничтожение ОУН. ^[45]Следуя этому и ряду аналогичных приказов, НКГБ УССР объявил 23 мая 1941 года, что задержал и погрузил в товарные вагоны для отправки в ссылку 11476 человек. ^[46] 31 мая 3-е (Секретно-политическое) управление НКГБ СССР выпустило ориентировку по антисоветским националистическим организациям, действующим на бывших польских территориях. Оно назвало ОУН как наиболее активную и описало ее тесные связи с Абвером и украинской эмиграцией на Западе. По данным, приведенным в ориентировке, после присоединения Западной Украины, та часть ОУН, которой руководил Степан Бандера, перенесла свой штаб из Львова в Краков, который был также местонахождением крупного подразделения Абвера, со школой и тренировочными лагерями для членов ОУН — по шпионажу, саботажу, диверсиям и организации подрывной деятельности. После окончания обучения отобранные выпускники направлялись в полк Бранденбург-800 германских специальных войск для дополнительной подготовки, после которой перебрасывались с заданиями на Советскую Украину — либо группами, либо поодиночке. Эта ориентировка НКГБ также обвиняла духовенство украинской, или униатской греко-католической, церкви в поддержке ОУН. В связи с тем, что к этому времени большинство украинского населения западных областей ненавидело советский режим и стремилось к независимости, они, вместе с духовенством часто рисковали сотрудничать с ОУН — организацией, которую считали патриотической и борющейся за независимость. ^[47]

15 июня 1941 года комиссар НКГБ Серов доложил о результатах о его операций против оуновцев за период с января 1941 года. Хотя было ликвидировано шестьдесят три политических и уголовных банды с арестами 273 членов, а также 212 их пособников, Серов признал, что значительное число этих банд все еще активно действовали в Львовской, Ровненской и Дрогобычской областях. ^[48] То же самое имело место в Тернопольской и Волынской областях. Что озабоченность Серова была обоснованной, видно из директивы НКГБ УССР, которую Меркулов выпустил буквально за несколько часов до немецкого нападения. Явно недовольный безуспешными попытками НКГБ обуздать ОУН, Меркулов предлагает провести новую широкомасштабную операцию, направленную на аресты и высылку «контрреволюционных элементов, особенно членов ОУН». Директива заканчивалась следующим приказом: «Немедленно телеграфируйте даты, к которым вы можете подготовить такую операцию». Но у адресатов уже не было возможности, чтобы рассмотреть этот приказ, потому как ко времени его получения началось немецкое вторжение. Одновременно с этим, активисты ОУН всеми своими силами стали сеять панику и вести диверсионную работу в тылу советских войск. ^[49]