Василий Гордиевский усердно работал на Управление «С» — отдел нелегальной разведки ПГУ. А еще он начал крепко пить — что вовсе не считалось серьезным недостатком, ведь в органах разведки высоко ценили способность поглощать после работы водку в огромных количествах и при этом держаться на ногах. Как специалист по нелегалам, он переезжал с места на место под разными вымышленными именами, служил в подпольной сети, передавал сообщения и деньги другим тайным агентам. Василий никогда не рассказывал младшему брату о своей деятельности, лишь ронял намеки, из которых можно было понять, что ему доводилось бывать в разных экзотических странах: Мозамбике, Вьетнаме, Швеции и ЮАР.
Олег надеялся, что и его вслед за братом отправят в это волнующее зарубежное подполье. Но вместо этого его определили в Управление «С» в Москве, где ему предстояло готовить документы для других нелегалов. 20 августа 1963 года, старательно скрывая разочарование, Гордиевский надел свой лучший костюм и явился на службу в штаб КГБ. Этот комплекс зданий неподалеку от Кремля — полутюрьма-полуархив — был кипучим руководящим центром советской разведки. Сердцем этой единой системы было зловещее здание на Лубянке — дворец в классицистическом стиле с элементами барокко, изначально построенный как доходный дом страхового общества «Россия». В подвалах этого здания находились пыточные камеры КГБ. Сами кагэбэшники называли свой главный корпус Монастырем или просто Центром.
Вместо того чтобы отправиться засекреченным агентом в какие-нибудь заманчивые заграничные края, Гордиевский уныло перекладывал бумажки и, как «раб на галерах», заполнял бланки. Каждому нелегалу требовалось создать фальшивую личину, которая выглядела бы убедительно, — по сути, вызвать из небытия нового человека с полностью вымышленной биографией и поддельными документами. Каждого такого нелегала полагалось опекать, инструктировать и финансировать, а для этого задействовалась сложная сеть условных сигналов, шпионских тайников и моментальных передач. Особенно перспективной страной для внедрения нелегалов считалась Британия, поскольку там не существовало внутренних паспортов и единой системы гражданской регистрации. К главным мишеням относились и Западная Германия, Америка, Австралия, Канада и Новая Зеландия. Олег, попавший в германский отдел, целыми днями придумывал биографии несуществующим людям. Два года он жил в мире двойных жизней, отправлял за границу новых шпионов с поддельными именами и паспортами и встречал тех, кто оттуда возвращался.
В Центре то и дело появлялись живые призраки — герои советской разведки, уже впавшие в старческое слабоумие. В коридорах Управления «C» Гордиевского познакомили с Кононом Трофимовичем Молодым, известным как Гордон Лонсдейл, — одним из самых успешных в истории разведчиков-нелегалов. В 1943 году КГБ завладел документами умершего канадского ребенка по имени Гордон Арнольд Лонсдейл и передал их Молодому, который вырос в Северной Америке и безупречно говорил по-английски. В 1954 году Молодый-Лонсдейл поселился в Лондоне и, прикидываясь общительным предпринимателем, торговцем музыкальными автоматами и жевательной резинкой, создал так называемое Портлендское шпионское кольцо — сеть завербованных осведомителей, которые занялись сбором секретных данных, связанных с военно-морским флотом. (Перед отъездом из Москвы кагэбэшный дантист просверлил ему в зубах несколько лишних дырок, и потому Молодому достаточно было просто открыть рот и продемонстрировать эти фирменные кагэбэшные полости, чтобы удостоверить свою личность в глазах других советских шпионов.) После слива информации одним кротом из ЦРУ Молодого арестовали и признали виновным в шпионаже, хотя даже в ходе процесса британский суд так и не выяснил его настоящее имя. Молодый вернулся в Москву незадолго до того, как его встретил Гордиевский: его обменяли на британского предпринимателя, арестованного в Москве по обвинению в шпионаже. Не менее легендарной фигурой был Вильям Генрихович Фишер, он же Рудольф Абель, — нелегал, получивший за свою шпионскую деятельность в США приговор к тридцати двум годам тюремного заключения и обменянный в 1962 году на Гэри Пауэрса — летчика сбитого над территорией СССР самолета U-2.