В 1986 году Литвиненко перешел из МВД в КГБ СССР, в отдел, занимавшийся борьбой с контрабандой и хищениями оружия и боеприпасов. В 1988 году Литвиненко был переведен в органы контрразведки КГБ. При происходивших в конце 1991 года реорганизациях аппарата КГБ Литвиненко был переведен в Москву, где в результате «перестройки» системы безопасности Российской Федерации возникла Федеральная служба безопасности, или ФСБ. 1992–1993 годы отличались, как известно, резким подъемом всех видов преступности, появлением этнических мафий, рэкета, заказных убийств и т. д. Обычная милицейская служба деградировала, и ФСБ стала выполнять множество новых функций борьбы с организованной преступностью. Литвиненко, уже в звании майора, специализировался на борьбе с терроризмом и организованной преступностью.
У Александра и Натальи Литвиненко к этому времени были сын Саша, родившийся в 1985 году, и дочь Соня, родившаяся в 1991 году. В Москве в 1993 году Александр Литвиненко неожиданно ушел от жены и семьи и стал жить с другой женщиной, Мариной. Оформить развод и новый брак в те годы было нетрудно. В недавнем интервью газете «Известия» Наталья Литвиненко сказала, что ее бывший муж не видел свою первую семью шесть лет, «он не звонил, не писал, не платил алименты». Она снова увидела его уже только по телевидению в конце 1998 года, во время пресс-конференции, на которой Литвиненко с группой других офицеров ФСБ рассказал о якобы полученном приказе физической ликвидации Бориса Березовского. После этой пресс-конференции Наталья Литвиненко позвонила своему бывшему мужу, и он стал навещать первую семью, подружившись с сыном Сашей, которому было уже 13 лет и который был очень похож на отца.
Александр Литвиненко познакомился с Борисом Березовским в 1994 году во время расследования теракта, организованного для убийства олигарха, который в то время боролся за владение дилерской фирмой «ЛогоВАЗ» и Московской независимой вещательной корпорацией (МНВК и телеканал «ТВ-6 Москва»), Березовского пытались убить 7 июня 1994 года с помощью радиоуправляемой мины. Мина была заложена в автомобиле, стоявшем рядом с воротами дома приемов «ЛогоВАЗа». Ее взорвали, когда «мерседес» Березовского проезжал мимо ворот. Водитель «мерседеса» был убит, Березовский, его телохранитель и восемь прохожих получили ранения. Заказчики и исполнители этого теракта не были найдены. При расследовании Литвиненко несколько раз встречался с Березовским для уточнения разных деталей и предложил ему свои услуги по связи с ФСБ. Олигарху, безусловно, был очень полезен «свой» человек в этой организации. Сотрудничество, по-видимому, хорошо оплачивалось, так как к концу 1998 года, когда первая жена Литвиненко Наталья снова с ним встретилась, он ей сказал: «За нами большие деньги. У нас свои суды, свои управления» [25] . К этому времени он уже смог купить квартиру в Москве, приобрести машину и построить дачу для своей новой семьи. У них с Мариной в 1994 году родился сын, названный Толей.
В марте 1995 года Березовский оказался главным подозреваемым по делу об убийстве генерального директора Общественного российского телевидения Владислава Листьева. В офисе Березовского был произведен обыск, и его самого несколько раз вызывали на допросы. В этот период Литвиненко в качестве подполковника ФСБ активно помогал Березовскому перевести все подозрения на президента АО «Группы Мост» Владимира Гусинского. Гусинский тогда контролировал соперничавшие с ОРТВ московские телеканалы, опиравшиеся на поддержку мэра Москвы Юрия Лужкова.
В 1995 году Александр Литвиненко в составе спецназа ФСБ участвовал в военных операциях в Чечне и был ранен. В 1997 году он был переведен во вновь созданное Управление по разработке преступных группировок и организаций (УРПО), которое считалось наиболее засекреченным подразделением ФСБ. Он получил должность старшего оперативного сотрудника, заместителя начальника 7-го отдела.
Широкая публика узнала о подполковнике ФСБ Литвиненко 18 ноября 1998 года, когда он вместе с группой офицеров ФСБ провел в Москве пресс-конференцию, которую транслировал телевизионный канал ОРТ, принадлежавший Борису Березовскому. Выступавшие сообщили о том, что в ноябре 1997 года, то есть почти год назад, они якобы получили от руководителей УРПО приказ убить Березовского, который в то время был заместителем секретаря Совета безопасности РФ. Однако Литвиненко и его товарищи отказались выполнять приказ, несмотря на угрозы начальников. Литвиненко на этой пресс-конференции присутствовал с открытым лицом и был представлен как подполковник ФСБ. Пять других офицеров не были представлены по именам и их лица были закрыты.
В ноябре 1998 года Березовский уже не был заместителем секретаря Совета безопасности. Но он занимал более ответственный пост председателя Исполнительного секретариата СНГ. Это назначение было сделано на заседании глав государств — участников СНГ 29 апреля 1998 года по предложению президента Украины Леонида Кучмы. Большинство обозревателей отнеслись к заявлениям Литвиненко и его товарищей очень скептически. Убийство заместителя секретаря Совета безопасности РФ не могло быть инициативой УРПО или даже ФСБ, председателем которой был тогда генерал-полковник Николай Ковалев.
В ноябре 1998 года ФСБ руководил уже Владимир Путин. Он был сильно раздражен этой пресс-конференцией, компрометирующей всю организацию. Однако никаких расследований или наказаний участников прессконференции по линии ФСБ не стали проводить. Березовский в то время был слишком влиятельной фигурой и лидером группы олигархов, которая организовывала и финансировала переизбрание Бориса Ельцина на второй срок в июле 1996 года. Тем не менее Путин не мог оставить обвинения, выдвинутые на пресс-конференции, без последствий. Секретное Управление по разработке преступных группировок и организаций было вскоре просто расформировано, и офицеры УРПО распределены по другим отделам ФСБ. Для решения тех же проблем были созданы более мелкие «спецгруппы», в одну из которых перевели Литвиненко. В марте 1999 года Литвиненко обвинили в превышении должностных полномочий и избиении заключенных во время допросов. Он был помещен в СИЗО «Лефортово».
В ноябре 1999 года суд вынес оправдательный приговор. Однако Литвиненко сразу же арестовали снова и поместили в СИЗО Бутырской тюрьмы. В начале 2000 года дело было прекращено и Литвиненко вышел из тюрьмы, предварительно дав подписку о невыезде. В УРПО против него начали третье уголовное дело с новыми свидетелями, пострадавшими при допросах. Литвиненко был всегда очень несдержан и вспыльчив. Новое дело грозило заключением, так как главный покровитель Литвиненко Борис Березовский, избранный в декабре 1999 года в Государственную думу по Карачаево-Черкесскому одномандатному избирательному округу № 15, уже конфликтовал с новой администрацией президента РФ Владимира Путина. Против Березовского было начато несколько дел в Прокуратуре РФ, в основном финансового характера. Подав в отставку с поста депутата Думы, Березовский лишился иммунитета. Его начали вызывать к следователям Генеральной прокуратуры РФ по «делу Аэрофлота» и некоторым другим, пока еще в качестве свидетеля. Березовский срочно продал многие свои российские активы, в частности, свою долю в компании «Сибнефть» Роману Абрамовичу и в октябре уехал на юг Франции, в свою виллу, с намерением не возвращаться в Россию. До отъезда Березовский уговорил Литвиненко бежать из России, пообещав ему финансирование и работу в США. Каким образом этот «побег из России» завершился приземлением в Лондоне, рассказывалось ранее.