В 2005 году, отвечая на вопрос журналиста о совместной службе с президентом Путиным, Чемезов заметил: «Зачем отрицать то, что было? Действительно, мы работали в ГДР в одно время. C 1983-го по 1988 г. я возглавлял представительство объединения «Луч» в Дрездене, а Владимир Владимирович приехал туда в 1985 году. Жили в одном доме, общались и по службе, и по-соседски». С разведкой, однако, у обоих не сложилось; пришлось возвращаться на родину.
Чемезова зачислили в 11-й отдел печально известного 5-го управления КГБ СССР (Управление по защите конституционного строя). Отдел этот был создан в 1977 году для контроля над международным спортивным обменом. Его сотрудники обеспечивали безопасность Олимпиады-1980. Чемезова встретили в этом отделе неласково, так как считалось, что он был ставленником нелюбимого многими генерала Кубышкина, начальника инспекторского управления.
В КГБ существовало неписаное правило: сотрудник периферийных органов переводился в центральный аппарат на должность на несколько ступеней ниже той, которую он занимал по прежнему месту службы. А Чемезов получил ту же должность – старший оперативный уполномоченный, видимо, потому, что прибыл в Москву из Дрездена. Кроме того, Чемезова, как офицера действующего резерва, назначили заместителем генерального директора «Союзспортобеспечения» – в ведомство, занимавшееся закупкой спортивной одежды и инвентаря за границей для советских спортсменов. И квартиру Чемезову дали сразу, хотя многие московские сотрудники годами ждали улучшения жилищных условий. В «Союзспортобеспечении» наиболее близкие отношения у Чемезова сложились с генеральным директором Виктором Галаевым, в прошлом комсомольским работником, начальником одного из спортивных управлений Спорткомитета СССР и секретарем парткома этого ведомства.
В начале 1990-х Галаев и Чемезов якобы занялись через посредников в Санкт-Петербурге поставками из США куриных окорочков, или, как тогда говорили, ножек Буша. Этот бизнес не мог работать официально, так как Галаев и Чемезов были госслужащими. И вот однажды, как рассказал в книге Владимир Прибыловский, «бизнесмены» якобы потеряли 100 тыс. долл., а точнее, их украла структура, которую «крышевала» могущественная казанская группировка. Далее Чемезов вышел на сотрудника 5-го управления КГБ Александра Петровича Евдокимова, бывшего куратора МВД СССР по линии Управления «3В» КГБ СССР. Евдокимов был близко знаком с верхушкой чеченской мафии, действующей в Москве в начале 90-х годов. Однако для чеченской ОПГ сто тысяч были небольшой суммой. Связываться из-за этих денег с Санкт-Петербургом Евдокимов не стал. Оставалась последняя надежда – на старого знакомого по Дрездену. А дальше – догадайтесь сами.