В предыдущие месяцы поток жителей Восточной Германии, бежавших на Запад через Западный Берлин, обрел характер стихийного бедствия. К 1961 году массовый исход немцев из страны, где утвердился коммунистический режим, достиг пика: количество беглецов насчитывало 3,5 миллиона, что составляло приблизительно 20 процентов от всего населения ГДР.
Проснувшись на следующее утро, Гордиевский обнаружил, что Восточный Берлин наводнен бульдозерами. Правительство ГДР по наущению Москвы перешло к радикальным мерам, чтобы перекрыть поток беглецов: началось возведение Берлинской стены — физического барьера, призванного отрезать Западный Берлин от Восточного и от остальной Восточной Германии. «Антифашистская защитная стена» (как она называлась официально) была в действительности внешней тюремной границей, и власти Восточной Германии строили ее для того, чтобы удерживать внутри собственных граждан. Берлинская стена — эти 240 километров бетона и проводов с бункерами, противотранспортными рвами и ограждениями из проволочной сетки — явилась материальным воплощением «железного занавеса» и стала одним из самых отвратительных сооружений, когда-либо возводившихся руками человека.
Гордиевский, застыв от ужаса, наблюдал за тем, как восточногерманские рабочие разрушали проезжую часть улиц, примыкавших к границе, а солдаты разворачивали мотки колючей проволоки — километры проволоки. Кое-кто из восточных немцев, видя, как единственный путь к побегу быстро перекрывается, совершал отчаянные попытки вырваться на свободу — смельчаки лезли на баррикады и пытались переплыть каналы, которые кое-где служили границей. Военные, выставленные вдоль границы, получили приказ стрелять по каждому, кто попытается бежать с востока на запад. На двадцатидвухлетнего Гордиевского новая стена произвела неизгладимое впечатление: «Один только физический барьер, охраняемый вооруженными пограничниками на дозорных вышках, мог удержать восточных немцев в их социалистическом раю и не дать им сбежать на Запад».
Хотя Гордиевского и потрясло начавшееся в одночасье возведение Берлинской стены, это потрясение не помешало ему неукоснительно выполнить задание, полученное от КГБ. Страх перед властью срабатывал как инстинкт, а привычка повиноваться давно и прочно укоренилась в сознании. Управление «С» назвало ему имя одной немки, бывшей осведомительницы КГБ; задача Гордиевского состояла в том, чтобы повидаться с ней и выяснить, готова ли она и дальше поставлять сведения. Гордиевский раздобыл ее адрес в местном полицейском участке. Женщина средних лет, открывшая ему дверь, нисколько не удивилась неожиданному визиту незнакомого молодого человека с букетом цветов. За чашкой чая она ясно дала ему понять, что готова продолжать сотрудничество с КГБ. Гордиевский сразу же написал свой первый отчет для КГБ. Лишь спустя несколько месяцев до него дошел смысл тогдашнего поручения: «Проверяли на самом деле не ее, а меня».
На Рождество он связался с Василием, который жил под подложным именем в Лейпциге. Олег не стал рассказывать Василию, как ужаснуло его строительство Берлинской стены. Старший брат был уже профессиональным кагэбэшником и не одобрил бы подобной идейной шаткости. Как их мать таила подлинные чувства от мужа, так и братья не делились друг с другом секретами: Олег понятия не имел о том, чем в действительности занимается в ГДР Василий, а Василий не догадывался о том, что творится в душе у Олега. Братья сходили на концерт, где исполняли «Рождественскую ораторию», и Олег остался «под сильным впечатлением». По контрасту Россия вдруг показалась ему «духовной пустыней», где можно слушать лишь одобренных властями композиторов, а «классово чуждую» церковную музыку — в том числе Баха — считают упадочной и буржуазной, поэтому она под запретом.
На Гордиевского глубоко повлияли несколько месяцев, проведенные в Восточной Германии: он стал свидетелем масштабного физического и символического разделения Европы на два враждебных идейных лагеря; он вкусил культурных плодов, остававшихся для него запретными в Москве; наконец, он приступил к шпионской деятельности. «Я очень радовался тому, что уже немного познакомился с работой, которая мне, может быть, предстояла, если я когда-нибудь буду работать на КГБ».