В 1935 году его назначили на должность теперь уже официального военного атташе в германское посольство в Москве.
Обосновавшись в особняке в Хлебном переулке, 28, что недалеко от Арбата, Кестринг, как, впрочем, и другие сотрудники военного, морского и авиационного атташатов, использовал любую возможность для сбора сведений по широкому кругу военно-экономических вопросов, так или иначе связанных с обороноспособностью СССР. Немцев интересовали, прежде всего, стратегический военный потенциал Советского Союза, дислокация военных объектов, транспортных узлов, электростанций, пропускная способность и состояние мостов и дорог и т. п.
Однако работать германской разведки приходилось в условиях жесткого контрразведывательного режима. С одной стороны, каждый их шаг немцев, а тем более, контакт с советскими гражданами фиксировался. Да и последние старались избегать несанкционированного общения с иностранцами.
Все попытки извлечения нужной информации из советских газет тоже закончились неудачей. Перечень сведений, не подлежащих оглашению в печати, был огромным, а цензура демонстрировала повышенную бдительность.
В столь непростых для себя условиях германские спецслужбы сделали основную ставку на легальную разведку с позиций дипломатических представительств своей страны в СССР. Центрами шпионажа стали посольство в Москве, а также консульства в Ленинграде, Киеве, Тбилиси, Харькове, Одессе, Новосибирске и Владивостоке. А под прикрытием должностей типа атташе, советников, секретарей и т. д. работала целая группа немецких разведчиков. Все они были, подобно Кестрингу, не новичками в этом деле и, что самое главное, хорошо знали страну пребывания, ее язык и народ, поскольку многие из них родились в России или Прибалтике, получили здесь образование и даже имели родственников. Пользуясь своей дипломатической неприкосновенностью, они развили бурную деятельность, пытаясь всеми доступными средствами получить любую информацию об оборонном потенциале Советского Союза.
Поэтому повышенной популярностью у германских «дипломатов» в Советском Союзе пользовались различные светские мероприятия, а также экскурсии и поездки по стране. Любил их и шестидесятилетний Кестринг. Поведения «Кесаря» (под этим именем он фигурировал в документах советской контрразведки) во время подобных «туристических» поездок колоритно описал один из секретных сотрудников НКВД, который под видом журналиста стал «случайным попутчиком» генерала во время его продолжительного путешествия по СССР по железной дороге.
«Генерал Кестринг — человек умный, хитрый, чрезвычайно наблюдательный и обладающий хорошей памятью. По-видимому, он от природы общителен, но общительность его и разговорчивость искусственно им усиливаются и служат особым видом прикрытия, чтобы усыпить бдительность собеседника. Он задает не один, а десятки вопросов самых разнообразных, чтобы скрыть между ними те два или три единственно существенных для него вопросов, ради которых он затевает разговор. Он прекрасный рассказчик, но и то, что он говорит, обычно ведет к совершенно определенной цели, причем так, что собеседник не замечает этого. В течение часа или двух он может засыпать собеседника вопросами, рассказами, замечаниями и опять вопросами. По первому впечатлению это кажется совершенно непринужденной беседой, и только потом становится ясным, что вся эта непринужденность и видимая случайность на самом деле вели к какой-то определенной цели».