Однако еще в 1934 году Сталин начал втайне рассматривать альтернативный путь противодействия германской угрозе, а именно, искать договоренностей с Гитлером, а не организации системы коллективной безопасности против него. На заседании Политбюро в начале июля 1934 года, вскоре после расстрела начальника штаба штурмовиков Эрнста Рема и еще около 180 человек во время проведенной Гитлером «ночи длинных ножей», Сталин, как говорят, воскликнул: «Слышали новости из Германии? Как Гитлер избавился от Рема? Молодец, этот Гитлер! Он показал, что надо делать с политическими противниками!» Решение Сталина ликвидировать всего через несколько месяцев после этого разговора Кирова, своего главного потенциального соперника, может быть, в какой-то мере обязано примеру Гитлера. Оценка Сталиным «соотношения сил» на Западе (концепция, которая, вопреки традиционной оценке баланса сил, учитывала политическую волю и военную мощь) тоже отражала его растущее уважение к Гитлеру. Сталин не верил в возможность долговременного союза с каким бы то ни было капиталистическим государством. Он был убежден, как того требует постулат марксистско-ленинской веры, что естественное желание всех капиталистов состоит в организации заговоров против Страны Советов. Но в тот момент внутренние противоречия раздирали капиталистический мир. Именно эти противоречия и были шансом для России. Известная ненависть Гитлера к марксизму вела к тому, что для СССР союз с нацистской Германией был делом гораздо более трудным, чем альянс с буржуазными демократиями. Но Сталин, казалось, надеялся, что Гитлер как достаточно опытный практик реальной политики осознает обоюдные выгоды нацистско-советского разделения Восточной Европы на сферы влияния.
В январе 1937 года глава советской торговой миссии в Берлине Давид Канделаки, действуя на основании инструкций Сталина и Молотова (Литвинов и не упоминался), начал прощупывать почву для заключения советско-германского политического договора, переговоры по которому должны были вестись тайно. Но в то время Гитлер не проявил интереса к такой возможности. Однако когда в сопровождении резидента НКВД в Берлине Канделаки возвратился в Москву для доклада Сталину, он дал, по словам Кривицкого, оптимистическую оценку перспектив соглашения с Германией. Правда, его оптимизм мог быть обусловлен нежеланием признать неудачу своей миссии. Ежов говорил Кривицкому: «Германия сильна. Она сейчас самая сильная страна в мире. Такой ее сделал Гитлер. Кто может в этом сомневаться? Кто, будучи в здравом уме, может с этим не считаться? У Советской России есть только один путь.» Он также упомянул, что Сталин говорил ему: «Мы должны договориться с такой сильной страной, как нацистская Германия.»
Поступавшие Сталину из нацистской Германии донесения были менее надежными по сравнению с другими странами, хотя до прихода к власти Гитлера советская внешняя разведка действовала в этой стране с широчайшим размахом. Коммунистическая партия Германии, крупнейшая компартия на Западе, организовала целую сеть из нескольких тысяч рабкоров (сокращение от «рабочий корреспондент»), открытой целью которых — как во Франции и других странах Европы — было сообщать коммунистической прессе об условиях труда. Рабкоры, однако, имели и более секретную задачу — добывать техническую информацию, которая использовалась для промышленного и военного шпионажа. В 1930 году Ганс Киппенбергер, член Политбюро КПГ, ответственный за связи партийного подполья с советским разведывательным аппаратом, был избран депутатом парламента Германии. В течение следующих трех лет, до захвата власти нацистами, он продолжал свою разведывательную работу, пользуясь защитой, которую ему обеспечивали парламентский иммунитет, и членство в комиссии по военным делам рейхстага. Берлин был главной базой на Западе операций Отдела международных связей Коминтерна и центром передовых организаций и информационной империи Мюнценберга. В Берлине также располагалась значительная, высоко профессиональная паспортная служба, которая помогала агентам ОГПУ, Четвертого Управления и Отдела международных связей Коминтерна по всей Европе и за ее пределами в получении паспортов и разработке «легенд» (фальшивых прикрытий с тщательно выверенными деталями биографических данных и поддельными документами). Ганс Райнерс, один из специалистов по паспортам этой службы, впоследствии показал на примере некоего «Ивара Мюллера», какое огромное внимание оказывается деталям:
«Мюллер не мог запросто возникнуть из ниоткуда, имея в кармане лишь паспорт на свое имя. Он должен был иметь основные документы, удостоверяющие его личность, например, свидетельство о рождении, справки о местах работы, книжку социального страхования и т.п. Все эти документы, удостоверяющие личность, называются комплектом, а для того, чтобы комплект был полным, надо привлечь к делу историка, географа, специалиста по методам работы полиции…