Так уж сложилась судьба у Судоплатова, что борьба с украинским национализмом стала одним из главных направлений его деятельности — и как «рядового» разведчика, и как одного из руководителей советской разведки. Его борьба с ОУН не закончилась уничтожением Коновальца. Во время войны и в первые послевоенные годы уже в качестве начальника Четвертого управления МГБ он будет лично руководить разгромом националистического подполья на Западной Украине.

В декабре 1938 года угроза ареста нависла и над Судоплатовым.

— На партсобрании поставили вопрос о моей связи с арестованными руководителями разведки, в том числе с Балицким, Горожаниным, благодаря которым я и оказался в свое время в Москве, — вспоминает Павел Анатольевич.

Вскоре на заседании партбюро принимается почти единогласно (воздержался только что возглавивший разведку П. М. Фитин) решение об исключении из партии.

До очередного партийного собрания, которое наверняка бы утвердило решение партбюро, оставалось несколько дней. Ну а потом, конечно, неизбежный арест.

И вдруг — вызов к Берия.

— Мне докладывают, что вы ни черта не делаете. Хватит валять дурака. Едем сейчас же в ЦК, — заявил тот.

В машине Лаврентий Павлович не проронил ни слова. Но Судоплатов понял: снова едут к Сталину.

— Докладывайте вопрос, — тихо обратился Сталин к Берия.

— Товарищ Сталин, после вашего указания мы разоблачили тех, кто обманывал партию. Сегодня мы решили обновить руководство разведкой, укрепить наши агентурные позиции за рубежом…

— Сейчас надо сосредоточиться на том, чтобы обезглавить троцкистов, — прервал Берия Сталин. — Надвигается война, а они работают зачастую с немцами, заодно с ними. Вам, товарищ Судоплатов, мы поручаем лично возглавить и провести эту операцию. Выезжайте на место, подбирайте людей, партия никогда не забудет тех, кто будет участвовать в этой операции, и навсегда обеспечит их самих и их детей. Вы назначаетесь заместителем начальника разведки для того, чтобы использовать весь потенциал разведывательных органов как военных, так и по линии НКВД. Но помните: вся ответственность целиком ложится на вас. Мы спросим с вас.

В тот же день был подписан приказ о назначении. Вместо изгнания из партии и ареста Судоплатов получил звание майора государственной безопасности. С только что вернувшимся из-за границы Эйтингоном он приступил к работе. Спустя три месяца появился план операции под кодовым названием «Утка».

— Было принято, — говорит Судоплатов, — беспрецедентное решение: моему заместителю Эйтингону разрешили действовать абсолютно самостоятельно с правом выбора и вербовки агентуры без согласования и без санкции Центра. Ему под личную отчетность выделялась астрономическая по тем временам сумма — триста тысяч долларов».

— О том, как убивали Троцкого, сегодня известно достаточно хорошо, и наверняка нет смысла повторяться, — говорит Павел Анатольевич. — Скажу лишь, что, когда первая попытка провалилась, я пережил немало волнений.

Берия узнал о провалившейся попытке из сообщений ТАСС и вызвал Судоплатова к себе на дачу в Петрово-Дальнее. Когда тот приехал, Берия обедал вместе со своими заместителями Кругловым и Серовым. Прервав обед, он вышел к Судоплатову, чтобы проанализировать причины неудачи.