В 1990 г. был переведен из Ленинграда в Карелию. По версии генерала Калугина, это было связано с тем, что его бывшие подчиненные попали под подозрение после того, как Калугин выступил с резкой критикой КГБ на конференции «Демократической платформы в КПСС» в июне 1990 г. [162].
В июне 1992 г. Патрушев был назначен министром безопасности Карелии. Занимал эту должность до 1994 г. Его подчиненным в этом управлении был Рашид Нургалиев, который позднее служил под началом Патрушева в центральном аппарате ФСБ России. С 2004 по 2012 гг. Нургалиев был министром внутренних дел РФ. После этого он был назначен заместителем секретаря Совета безопасности РФ, то есть вновь стал подчиненным Патрушева.
В начале 1990-х гг. поддерживал связи с имевшими коммерческие интересы в Карелии петербургскими фирмами, созданными при участии бывших офицеров КГБ; в частности, в 1990 г. среди учредителей фирмы Виктора Иванова и Бориса Грызлова МП «Блок» значится подчиненный Н.Патрушева по УКГБ Карелии Валентин Чуйкин, а в декабре 1993 года среди учредителей фирмы Грызлова ТОО «Борг» присутствовала Е.Н.Патрушева (вероятно, его жена Елена).
В ноябре 1993 г. был выдвинут инициативной группой Министерства безопасности республики Карелия кандидатом в Совет Федерации первого созыва по двухмандатному Карельскому округу № 10, но снял свою кандидатуру (12 декабря 1993 членами СФ от Карелии были избраны председатель Верховного совета республики Виктор Степанов и председатель республиканского Совета министров Сергей Блинников).
В 1994 г. был переведен в Москву в центральный аппарат ФСК, где занял должности заместителя руководителя департамента — начальника организационно-инспекторского управления департамента по организационно-кадровой работе ФСК Федеральная служба контрразведки, предшественница ФСБ, существовала в 1993–1995 гг.).
По утверждению Александра Литвиненко, перевод в Москву был связан с тем, что в Карелии Патрушев попался на хищении и контрабанде карельской березы. Согласно Литвиненко, прокуратура Петрозаводска возбудила уголовное дело, по которому Патрушев проходил свидетелем, и от перехода в статус обвиняемого его спас директор ФСК Сергей Степашин, взяв в Москву[163].
С должности заместителя руководителя департамента — начальника организационно-инспекторского управления департамента по организационно-кадровой работе ФСБ был переведен на должность начальника управления собственной безопасности (УСБ) ФСБ России.
31 мая 1998 г. был назначен начальником Главного контрольного управления (ГКУ) президента РФ (УСБ вместо Патрушева возглавил Виктор Иванов).
11 августа 1998 г. указом президента РФ был назначен заместителем руководителя администрации президента РФ — начальником Главного контрольного управления президента РФ (главой АП в это время был Валентин Юмашев). Освобожден от должности в начале октября 1998 г.
6 октября 1998 г. назначен заместителем директора — руководителем департамента экономической безопасности ФСБ РФ. С начала 1999 г. — первый заместитель директора ФСБ России Путина.
9 августа 1999 г. указом президента Б.Н.Ельцина директор ФСБ Владимир Путин был назначен временно исполняющим обязанности главы правительства. В тот же день Патрушев был назначен вр.и.о. директора ФСБ России, а 17 августа 1999 г. — директором ФСБ России.
4 сентября 1999 г. в Буйнакске (Дагестан) произошел взрыв начиненного взрывчаткой автомобиля, вызвавший разрушение жилого дома: 9 сентября 1999 г. — ночной взрыв жилого дома на улице Гурьянова в Москве; 13 сентября — взрыв жилого дома на Каширском шоссе в Москве: 16 сентября — взрыв жилого дома в Волгодонске. Организаторами взрывов были объявлены чеченские сепаратисты. 22 сентября 1999 г. в Рязани жильцы одного из многоквартирных домов обнаружили минирование подвала неизвестными. Жильцы были эвакуированы, преступники объявлены в розыск. Однако 24 сентября Патрушев заявил, что минирование было учебным и проводилось сотрудниками ФСБ в целях тренировки бдительности[164]
30 сентября 1999 г. Патрушев был избран председателем совета руководителей органов безопасности и спецслужб государств — участников СНГ. 20 ноября 1999 г., в соответствии с занимаемой должностью, назначен одним из двух заместителей председателя Федеральной анти-террористической комиссии (председатель — премьер-министр Владимир Путин; с мая 2000 — Михаил Касьянов: другой заместитель — министр внутренних дел Владимир Рушайло).
В то время, когда Патрушев возглавлял ФСБ. произошли крупнейшие в истории России террористические акты: взрыв 9 мая 2002 в Каспийске, взрывы во время музыкального фестиваля в Москве (2003), захват заложников в театральном центре на Дубровке в Москве (2003), подрыв военного госпиталя в Моздоке (2003), взрыв электрички Минеральные Воды — Кисловодск (2003), взрыв в московском метро (2004), убийство президента Чечни Ахмата Кадырова (2004), взрывы двух пассажирских самолетов (2004), нападение на Назрань (2004), захват заложников в школе № 1 в г. Беслане (2004), вооруженное нападение на Нальчик (2005)и другие.
В период, когда Патрушев был директором ФСБ, погибли: в Чечне в результате отравления чеченский полевой командир иорданец Хаттаб (2002); в результате взрыва в Катаре бывший временный президент Чеч-ни-Ичкерии Зелимхан Яндарбиев (2004); в результате взрыва в Чечне террорист Шамиль Басаев (2006); в результате отравления в Лондоне бывший сотрудник ФСБ Александр Литвиненко (2006).
В августе 2003 г. в ходе учений ФСБ по «локализации террористических проявлений в условиях плоскогорья» Патрушев совершил в составе группы спецназа подъем на вершину Эльбруса на высоту 5642 метра.
6 апреля 2004 г. избран президентом Всероссийской федерации волейбола (прежний президент ВФВ Валентин Жуков стал первым вице-президентом, а председатель ВГТРК Олег Добродеев получил пост вице-президента). Занимал пост до октября 2009 г., когда президент Медведев заявил, что дал поручение заменить в течение месяца возглавляющих российские спортивные федерации чиновников на «профессионалов, уделяющих своему виду спорта 24 часа в сутки». Затем — председатель Наблюдательного совета Всероссийской федерации волейбола.
11 июля 2004 г. Путин подписал указ о реформировании ФСБ, по которому статус директора ФСБ России был приравнен к статусу министра. Функции ликвидированной Федеральной пограничной службы России были переданы ФСБ России, при которой была создана Пограничная служба. Кроме того, было упразднено Федеральное агентство правительственной связи и информации при президенте России, часть его функций была передана ФСБ России.
16 февраля 2006 г. президент Путин подписал указ о создании Национального антитеррористического комитета (НАК), который возглавил Патрушев.
7 января 2007 г. вместе с депутатом-полярником Артуром Чилингаровым и другими посетил Антарктиду и Южный полюс на вертолетах.
В 2007 г. ухудшились отношения между Патрушевым и тогдашним руководителем Федеральной службы по контролю за оборотом наркотиков (ФСКН) Виктором Черкесовым. Руководители ФСКН занимались техническим сопровождением расследования уголовных дел, в которые были вовлечены высокопоставленные сотрудники ФСБ. В октябре 2007 г. начальник Департамента оперативного обеспечения Федеральной службы по контролю за оборотом наркотиков (ФСКН) генерал-лейтенант Александр Бульбов и старший оперуполномоченный по особо важным делам Сергей Донченко были арестованы. Виктор Черкесов опубликовал в «Коммерсанте» статью[165], в которой публично заявил о наличии конфликта между ФСБ и ФСКН и обвинил ФСБ в давлении на Следственный комитет при Генеральной прокуратуре.
На следующий день после появления статьи Виктора Черкесова Владимир Путин посетил Федеральную службу безопасности, то есть поддержал Патрушева. Черкесов продержался во главе ФСКН до мая 2008 г. Генерал Бульбов просидел под следствием два года, получил три года условно за мошенничество, а в 2014 г. с него были сняты все обвинения.
8 апреля 2008 г. на заседании Национального антитеррористического комитета (НАК) Патрушев сказал, что информационную поддержку террористам «в немалой степени оказывают отдельные иностранные неправительственные организации». Патрушев не уточнил перечень организаций, подозреваемых в связях с террористами, однако его выступление восприняли как попытку дискредитировать иностранные НКО, работающие в России. Так, российский представитель Human Rights Watch Александр Петров потребовал от главы ФСБ доказательств причастности НКО к террористическим действиям, а директор российского отделения Всемирного фонда дикой природы назвал речь Патрушева «безответственной»[166].
12 мая 2008 г. после вступления в должность президента России Дмитрия Медведева Николай Патрушев был назначен секретарем Совета безопасности России.
В декабре 2012 г. Патрушев заявил, что в России отсутствуют предпосылки к возможным цветным революциям и пообещал не допустить реализации таких сценариев[167].
В 2013 г. Патрушев на заседании научного совета при СБ попросил его членов уделить «особое внимание» подготовке предложений «по укреплению национальной безопасности в духовно-нравственной сфере».
В июле 2014 г. санкции в отношении Патрушева ввел Европейский союз, в августе — Канада и Швейцария, в сентябре 2014 г. — Австралия.
В марте 2015 г. Патрушев на совещании по вопросам обустройства госграницы заявил о росте влияния финских националистических организаций на Россию через карельские некоммерческие организации (НКО). Представители власти Карелии были удивлены этим заявлением и заверили газету «Коммерсант», что у Патрушева «нет предпосылок для подобных заявлений»