Прошел годичные курсы повышения квалификации Высшей школы КГБ СССР по специальности «правовед»; окончил Высшие курсы КГБ при СМ СССР.
После окончания института непродолжительное время работал инженером в конструкторском бюро ЛКИ.
В органах государственной безопасности с 1974 г. Согласно официальной биографии, работал «в контрразведывательных подразделениях УКГБ СССР по Ленинградской области». Был младшим оперуполномоченным, начальником городского отделения, заместителем начальника райотдела, начальником службы по борьбе с контрабандой и коррупцией управления КГБ по Ленинграду и Ленинградской области.
Избирался депутатом Совета народных депутатов Петроградского района Ленинграда.
Был членом КПСС до ее запрещения в августе 1991 г.
Во время работы в Ленинградском УКГБ начальником Патрушева до 1989 г. был Олег Калугин, генерал-майор КГБ (в перестройку боролся за реформирование ведомства, с 1995 г. живет в США). Калугин вспоминает его, как энергичного, цеустремленнного и настырного сотрудника[161]
.В 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]