В ноябре 1937 года, после празднования двадцатилетия Октябрьской революции Судоплатова вызвали вместе со Слуцким к Ежову, тогдашнему наркому внутренних дел. Павел встретился с ним впервые и поразился неказистой внешности. Генеральный комиссар государственной безопасности был тщедушным недомерком с нездоровым цветом лица и колючим взглядом.
Задаваемые им вопросы касались самых элементарных для любого разведчика вещей и звучали некомпетентно. Чувствовалось, что нарком не знает самих основ работы с источниками информации. Более того, похоже, его вообще не интересовали раздоры внутри организации украинских эмигрантов.
Павел искренне считал, что просто не в состоянии оценить те интеллектуальные качества, которые позволили этому человеку занять столь высокий пост. Хотя к этому времени Павел был уже достаточно опытным профессионалом разведслужбы, но во всём, что касалось карьеры в высших эшелонах власти, оставался наивным человеком. Руководители, с которыми он сталкивался до сих пор, с такими, как возглавлявшие компартию Украины Косиор и Петровский, были высокоинтеллектуальными людьми широкого кругозора.
Выслушав его сообщение относительно предстоящих встреч с украинскими националистами, Ежов внезапно предложил, чтобы Судоплатов сопровождал его в ЦК.
Павел был поражен, когда их машина въехала в Кремль, допуск в который имел весьма ограниченный круг лиц. Его удивление ещё больше возросло, когда Ежов объявил, что их примет лично Сталин. Это была первая встреча Судоплатова с вождем. Ему было тридцать, и он не верил, что руководитель страны захотел встретиться с рядовым оперативным работником. После того как Сталин пожал Павлу руку, последний никак не мог собраться, чтобы четко ответить на вопросы. Улыбнувшись, Генеральный секретарь заметил:
— Не волнуйтесь, молодой человек. Докладывайте основные факты. В нашем распоряжении имеется двадцать минут.
— Товарищ Сталин, — последовал ответ, — для рядового члена партии встреча с вами — величайшее событие в жизни. Я понимаю, что вызван сюда по делу. Через минуту возьму себя в руки и смогу доложить основные факты вам и товарищу Ежову.
Хозяин кабинета, кивнув, спросил об отношениях между политическими фигурами в украинском эмигрантском движении. Судоплатов вкратце описал бесплодные дискуссии между украинскими националистическими политиками по вопросу о том, кому из них какую предстоит сыграть роль в будущем правительстве. Реальную угрозу, однако, представлял Коновалец, поскольку он активно готовился к участию в войне против СССР вместе с немцами. Слабость этой позиции заключалась в постоянном давлении на него и возглавляемую им организацию со стороны польских властей, которые хотели направить украинское национальное движение в Галиции против Советской Украины.
— Ваши предложения? — спросил Сталин. Ежов хранил молчание. Судоплатов тоже. Потом, собравшись с духом, Павел сказал, что сейчас не готов ответить.
— Тогда через неделю представьте свои предложения.
Аудиенция окончилась, Сталин пожал чекистам руки, оба вышли из кабинета.
Вернувшись на Лубянку, Ежов тут же дал Судоплатову указание — вместе с Шпигельглазом немедленно приступить к работе.
На следующий день Слуцкий как начальник Иностранного отдела направил докладную записку наркому. Там был подробно изложен план интенсивного внедрения в ОУН, прежде всего на территории Германии. Для этого, в частности, предлагалось направить трёх сотрудников украинского НКВД под прикрытием в качестве слушателей в нацистскую партийную школу. А для подстраховки — одного истинного националиста, не особо сообразительного.
— Ну что же, — ознакомившись с докладной запиской, заявил нарком Ежов. — Лично у меня нет вопросов. Но товарищ Сталин дал указание посоветоваться на этот счет с товарищами Коси-ором и Петровским, у которых могут быть свои соображения. Вам, Судоплатов, надлежит немедленно выехать в Киев, переговорить с ними и на следующий день вернуться в Москву.
Спустя два часа курьерским поездом Павел отправился по назначению. Вскоре позади растаяли окраины столицы, за окнами замелькали перелески, реки и поля…
Беседа проходила в кабинете Косиора, где присутствовал и Петровский. Оба проявили интерес к предложенной чекистами двойной игре. Однако более всего их заботило предполагавшееся тогда провозглашение независимой Карпатской Украинской республики.
Ровно через неделю после возвращения в Москву Ежов в одиннадцать вечера вновь доставил Судоплатова в кабинет к Сталину. На этот раз там находился Петровский, что не удивило Павла. За десять минут Судоплатов изложил план оперативных мероприятий против ОУН, подчеркнув главную цель — проникновение в Абвер через украинские каналы, поскольку германская разведка являлась главным противником в предстоящей войне.
Сталин попросил Петровского высказаться.