В 1962 году окончил Московский государственный институт международных отношений и поступил на службу в КГБ.
С 1966 по 1970 год Олег Гордиевский под прикрытием сотрудника консульского отдела посольства СССР в Дании служил офицером разведки КГБ. По его словам, окончательно разочаровался в роли, которую СССР играл в мире, после военного подавления Пражской весны 1968 года, вскоре после чего привлёк к себе внимание британской разведки в Дании.
С 1970 по 1972 год Олег Гордиевский служил в Москве в центральном аппарате разведывательного управления КГБ.
В 1972 году Олега Гордиевского вновь направили в Копенгаген. В 1973 году он стал заместителем резидента КГБ в Дании, а в 1976 году занял пост резидента.
С 1978 по 1982 год Олег Гордиевский служил в Москве в центральном аппарате разведывательного управления КГБ.
В 1982 году Олег Гордиевский получил назначение в посольство СССР в Великобритании. С января 1985 года Гордиевский исполнял обязанности резидента внешней разведки КГБ в Лондоне.
В 1985 году Олег Гордиевский попал под подозрение КГБ. Под предлогом повышения, его вызвали в Москву, отвезли в загородный дом КГБ, где, по его словам, его напоили психотропным наркотиком и допрашивали около пяти часов. По каким-то причинам, руководство КГБ не арестовало Гордиевского сразу, а оставило его под домашним арестом, из-под которого ему удалось сбежать, предварительно дав сигнал офицеру британской спецслужбы в посольстве в Москве. 20 июля 1985 года Гордиевский сумел перехитрить слежку КГБ и с помощью британской разведки бежал из СССР. Он проехал к границе с Финляндией, где его подобрали британские дипломаты и провезли через советские пограничные КПП в багажнике дипломатической машины. КГБ, его упустив, распространил историю, что он якобы был вывезен прямо из Москвы.
14 ноября 1985 года заочно приговорён «за измену Родине» к смертной казни с конфискацией имущества. Приговор к высшей мере наказания не был отменён и после распада СССР. Конфискация имущества отменена в 1989 году по просьбе жены Гордиевского Лейлы (в девичестве Алиевой), которую в качестве заложницы держали в СССР вместе с двумя дочерьми. Семья выехала из страны только шесть лет спустя после развала СССР.
Написал ряд книг об операциях, внутренней структуре и методах КГБ, а также о террористической и подрывной деятельности советского руководства в мире. Мемуары, «Следующая остановка — расстрел» переведены на русский язык и изданы в РФ.
Гордиевскому приписывается ключевой вклад в предотвращении ядерного удара в критический период «холодной войны» в 1983 году, во время проведения НАТО учений «Able Archer 83». Узнав от Гордиевского о разразившейся в Советском руководстве панике в связи с тем, что под видом учения Запад готовится к ядерному удару по СССР, Британия и США смогли так поменять параметры учения, что успокоили СССР. Президент Рейган даже на некоторое время неожиданно покинул Вашингтон.
Известный критик Кремля, особенно после прихода сотрудников КГБ к власти в РФ после отставки президента Ельцина. Был близким другом Александра Литвиненко в Англии. Довольно часто даёт интервью и комментарии о российской внешней и внутренней политике, деятельности российских спецслужб.