Гордиевский родился в 1937 году в семье сотрудника НКВД. Его отец к 1953 году дослужился до чина полковника и работал в Управлении учебных заведений. Брат Гордиевского Василий также служил в КГБ, в управлении «С» (нелегальная разведка) ПГУ. Сам Гордиевский по окончании школы поступил в МГИМО.
После окончания института в 1962 году Гордиевского приглашают на работу в ПГУ КГБ. В 1962–1963 годах он проходит обучение в разведшколе, а затем приступает к работе в управлении «С» ПГУ в 5-м отделе, занимавшемся нелегальной разведработой в странах Западной Европы. Правда, по ряду причин на роль нелегала молодой лейтенант Гордиевский не подошел, и был оставлен в аппарате управления, где, помимо служебных обязанностей, активно занимался общественной работой. В 1963–1964 годах он был культоргом управления и имел возможность общаться с такими известными нелегалами, как И. Ахмеров, К. Молодый, и другими.[56]
В 1966 году Гордиевский был командирован в Данию, где в копенгагенской резидентуре работал по линии «Н» (поддержка нелегалов). В то время, как, впрочем, и в дальнейшем, коллеги по работе характеризовали Гордиевского положительно. Вот как вспоминает о нем Б. Григорьев, работавший с Гордиевским в управлении «С»:
«Следует признать, что Гордиевский был довольно-таки незаурядной личностью с большими задатками. Неплохое общее образование, полученное им в МГИМО и в школе КГБ, его несколько академический, по довольно подвижный ум, чрезвычайная усидчивость и трудоспособность, интерес к истории и философии, серьезная начитанность выделяли его даже среди весьма образованной массы разведчиков и дипломатов. Немногословный, скрытный по характеру, сдержанный в выражении эмоций, со слегка старомодными манерами, он не «приклеивался» к какой-либо группе или кружку, а входил в них на правах свободного члена. Он не был завсегдатаем компаний, иг курил, почти не пил, испытывая явную скованность в общении со слабым полом, но букой не был. Страшно стеснялся своей застарелой болезни — гайморита. Держался всегда в тени, хотя был непомерно честолюбив, не стремился на партийные и другие выборные должности, никогда не злословил и не сплетничал, предпочитая отмалчиваться, если при нем заходил о ком-то разговор».
Подобное мнение высказывает о нем и М. Любимов, резидент КГБ в Дании с 1976 по 1980 год, являвшийся в 1976–1978 годах прямым начальником Гордиевского.
«Гордиевский импонировал мне своими обширными познаниями в области политики, истории и религии, датских нравов и обычаев, мне нравились его интеллигентность и покладистый характер. Мешало нам сблизиться его равнодушие к «богемной жизни»: я, грешным делом, люблю застолья и компании, он же мало с кем общался, предпочитая уединение и музыку. В советской колонии к Гордиевскому относились по-разному: одни ценили его вежливость и предупредительность, готовность помочь и чувство юмора, по кое-кто считал его двуличным, себе на уме».