В январе 1932 года Дейч вместе с женой Жозефиной приезжает в Москву, переводится из КПА в компартию нашей страны, а спустя несколько месяцев по рекомендации Коминтерна начинает работать в Иностранном отделе (ИНО) НКВД (внешняя разведка). Помимо родного немецкого и «рабочего» русского Дейч свободно владел английским, французским и итальянским языками. Мог объясняться на испанском и голландском.

В те годы в ИНО работали лишь около 150 человек, половина из которых — за границей. Разведка не располагала необходимой базой и временем для тщательной подготовки сотрудников. Поэтому люди с опытом и знаниями Дейча представляли для разведки значительный интерес. В ИНО Дейч прошел ускоренный курс подготовки разведчика-нелегала, а жена Жозефина освоила работу радистки.

В начале января 1933 года супругов направляют на нелегальную работу во Францию. Дейч, теперь уже «Стефан», становится помощником, а через некоторое время — заместителем резидента советской нелегальной разведки в этой стране. С позиций Франции он успешно выполняет специальные задания Центра в Бельгии, Австрии, Голландии и Германии. Однако основная работа ждала «Стефана» впереди.

Для советской разведки того времени большой интерес представляла Великобритания. В то же время после восстановления дипломатических отношений с Советским Союзом в 1929 году британские спецслужбы установили в отношении официальных советских представителей жесткий контрразведывательный режим. За сотрудниками советских учреждений в Лондоне велась интенсивная слежка, их телефоны прослушивались, контролировалась почтовая корреспонденция. Поэтому Москва приняла решение об активизации разведывательной работы в Великобритании с нелегальных позиций.

«Стефан» получает задание — обосноваться в Лондоне. В феврале 1934 года он переводится туда на нелегальную работу и для прикрытия становится студентом Лондонского университета, где совершенствует знания в области психологии.

Учеба в университете дала возможность заводить широкие связи среди студенческой молодежи. Будучи одаренной от природы, содержательной личностью, натурой притягательной, тонко чувствующей сущность и внутренний мир человека, «Стефан» пользовался этим даром так, как ему подсказывали его наблюдения и чутье. В Лондоне у него в полной мере проявилась такая важная черта профессионального разведчика, как умение отбирать нужных людей и терпеливо готовить их для работы на разведку. Он сосредоточил свои разведывательные интересы преимущественно на Кембриджском и Оксфордском университетах. Его, как разведчика, в первую очередь интересовали студенты, которые в перспективе могли стать надежными помощниками по разведывательной работе.

«Стефан» был первым советским разведчиком, который сделал твердую ставку на приобретение перспективной агентуры. Его неоценимая заслуга состоит в том, что он сумел создать и воспитать знаменитую «кембриджскую пятерку» разведчиков, в которую входили Ким Филби, Дональд Маклейн, Гай Берджес, Антони Блант и Джон Кернкросс.

В середине 1970-х годов Ким Филби говорил по поводу использования перспективной агентуры и о работе «Стефана» в данном направлении следующее:

«На момент вербовки у меня не было доступа ни к какой секретной информации, да и вообще ни к какой информации, кроме радио и газет. У меня не было работы. Я даже не знал, куда мне удастся устроиться, считал только, что мои надежды скорее всего могут быть связаны с журналистикой. И тем не менее меня завербовали. Единственное, что было известно обо мне сотруднику нелегальной разведки, это мое желание работать на дело коммунизма (даже в нелегальных условиях, если потребуется) да еще то, что я происходил из безукоризненной буржуазной семьи, получил буржуазное воспитание и образование.