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]
.