В 1927 г. Павел был переведен на более «высокую» должность в Харьков, где встретил любовь всей жизни, красавицу Э. Каганову. Она стала его супругой и прошла вместе с ним через тяжелые времена. Не оставив супруга до самого конца, она умерла у него на руках в 1988 г. Но это будет потом, а пока Судоплатов работал в Харькове. Среди прочего он занимался беспризорниками в детской колонии. Здесь уместно заметить эффективность, с которой советская власть справлялась с беспризорщиной. Она как явление была ликвидирована на всей территории необъятной страны и, кстати говоря, также быстро возродилась с распадом Советского Союза после 1991 г.
В 1933 г. на должность заместителя председателя общесоюзного ОГПУ в Москву позвали руководителя Главного политического управления УССР В. А. Балицкого. Он взял с собой Павла, определив его на место старшего инспектора в отделе зарубежной разведки. Начальником у него был А. X. Артузов, сумевший разглядеть в неопытном молодом человеке выдающиеся способности разведчика. Предложение стать агентом-нелегалом ему сделал не начальник, а его заместитель — А. А. Слуцкий. Судоплатов согласился и приступил к специальной подготовке, длившейся 8 месяцев. Далее последовало 1-е задание в новом качестве.
В это время во Львове произошло убийство одного из сотрудников ГПУ. Поскольку в нем оказались замешаны украинские националисты, то несколько поутихшая активность по их ликвидации вновь была активизирована. Предпринимались действия по внедрению в их ряды агентов. Один из таких «кротов», названный в книге Судоплатова «Спецоперации» Лебедем, отправился в зарубежную командировку с Павлом, который, по легенде, разочаровался в коммунистах.
По прибытии в Финляндию в июле 1935 г. молодого разведчика передали в ведение другого агента ГПУ — К. Полуведько. Не поставленный в курс дела относительно Судоплатова, он проявлял чрезмерную подозрительность к юноше и даже предлагал его ликвидировать. Как можно было ожидать, в Центре проигнорировали подобные рекомендации. Уже через 2 месяца иностранной жизни и контактов со связными руководителя всех украинских националистов полковника Е. М. Коновальца Судоплатов (псевдоним Павлусь) отправился в столицу Германии, где летом 1936 г. лично познакомился с главным оуновцем. После нескольких продуктивных встреч новый член организации поступил в нацистскую партийную школу, благодаря чему завел связи со многими активными украинскими «деятелями».
Павел все больше входил в доверие к Коновальцу, и встречи происходили все чаще. Вскоре Коновалец предложил Судоплатову поехать вместе с ним с инспекцией во Францию и Австрию. Так у советского разведчика появилась возможность встретиться в Париже со связным из Центра. Каково же было его удивление, когда при входе в столичное кафе он увидел свою ненаглядную Эмму. Иногда жизнь все-таки похожа на кино — достаточно вспомнить сцену встречи в кафе Штирлица со своей женой из «Семнадцати мгновений весны».