После учебы в Минске Патрушев вернулся в Ленинград и начал работать младшим уполномоченным в Октябрьском райотделе УКГБ. Чтобы поднять боевой дух сотрудников, начальник отдела Лев Коротышев заказал ростовой портрет Феликса Дзержинского и повесил его в коридоре. Сотрудники поставили под портретом пулемет «Максим», изъятый у торговцев нелегальным оружием.

Отдел контролировал центральный район Ленинграда, в котором работало несколько заводов, музеев и институтов. Каждому сотруднику давали вести дела оперативного учета, Патрушеву доверили курировать Ленинградский институт физической культуры. Коротышев вспоминал, что рекомендовал сотрудникам не доводить дело до ареста, а активнее использовать профилактические беседы. Это тоже было одной из идей Андропова: глава КГБ верил, что люди могут выступать против советской власти только по недомыслию или науськиванию из-за рубежа, а значит, дело спецслужбы — проникнуть во все сферы общества и по-отечески уберечь советских граждан от ошибки.

Патрушев быстро учился у Коротышева, добился его расположения, завязал хорошие отношения с коллегами и стал лидером футбольной команды отдела. Когда в 1983 году Коротышев уходил из отдела, благодарные сотрудники подарили ему прощальный адрес со словами: «Мы обещаем Вам, что наука Ваша не пропадет даром, что мы с честью и достоинством пронесем почетное звание Чекиста через нашу жизнь». К адресу прилагался фотомонтаж «Октябрьская дружина» — на нем Коротышев был изображен в образе древнерусского воеводы, а рядом с ним в два ряда стояли витязи — сотрудники отдела. Патрушев с щитом и мечом стоял самым первым. Примерно тогда же его назначили начальником отделения УКГБ города Кировска в Ленинградской области.

Кировск — небольшой город на Неве с небольшим отделом КГБ, но для Патрушева это было серьезное продвижение. Бывший генерал-майор Олег Калугин — диссидент из КГБ, пролоббировавший это повышение, — описывал его как энергичного, целеустремленного и амбициозного сотрудника. Иногда даже слишком амбициозного. Калугин рассказывал, что ему однажды пришлось осадить Патрушева, когда тот придумал провокацию, чтобы отправить в тюрьму кировского «клеветника» — обычного человека, который не стеснялся возмущаться очередями и неспособностью власти улучшить экономическую ситуацию в стране.

Патрушев продолжал расти по службе. В 1987 году его вернули в Ленинград и назначили начальником Петроградского районного отдела УКГБ. Он подобрал команду молодых оперативников и энергично принялся за дело. Для укрепления командного духа сотрудники разделились на две команды и еженедельно играли в футбол. Важным ежегодным ритуалом было празднования дня чекиста 20 декабря. Один из бывших подчиненных Патрушева Павел Кошелев вспоминал, как тот, несмотря на перестроечный сухой закон, раздобыл к празднику алкоголь и придумал организовать конкурс для сотрудников и их жен — стрельбу по мишеням из игрушечных пистолетов пулями с присосками. Неформально сотрудники называли свой отдел «ПетроЧК».

По мере разворачивания перестройки отделу пришлось адаптироваться к новым реалиям: больше времени уделять неформалам, молодежным движениям, а главное — кооператорам и зарождавшемуся тогда частному предпринимательству. Именно в это время чекисты, привыкшие контролировать любые возникающие в стране организации, завязали полезные связи, которые позволят им уйти в бизнес в 1990-е. Они старались выполнить привычную задачу — взять под контроль вышедшее из оцепенения общество, чтобы уберечь его от «ошибки». Чем дальше шла перестройка, тем сложнее им это давалось.

Руководство союзного КГБ на Лубянке вовсю било тревогу и рассылало на места приказы усилить бдительность и готовиться к защите государственного строя. «Реакционные империалистические круги, опасаясь упрочения позиций социализма, пытаются активно использовать процесс демократизации <…> в целях подрыва и ослабления советского социалистического общества», — писал в 1989 году глава КГБ Владимир Крючков.

Чтобы не выпускать ситуацию из-под контроля — и при этом формально не противоречить горбачевским инициативам, нацеленным на демократизацию, — многих сотрудников КГБ отправили баллотироваться на выборах народных депутатов в городские и республиканские советы. Патрушев, никогда не любивший публичности, избрался в совет депутатов Петроградского района Ленинграда. Никаких следов его депутатской деятельность не осталось. Возможно, он, как и его шеф Олег Калугин, попавший в областной совет за несколько лет до этого, просто приходил раз в месяц в свой кабинет и в одиночестве читал там газету. Более серьезных электоральных успехов у чекистов не было — в условиях гласности они раз за разом проигрывали более харизматичным и демократически ориентированным кандидатам.

В десятках мемуаров о тех событиях чекисты называют перестройку предательством, а слово демократия пишут в кавычках. В начале 1991 года КГБ в анкете для своих сотрудников спросил: «В чем вы видите основные причины кризисных явлений и трудностей, переживаемых нашей страной на современном этапе?» 90 процентов ответили, что трудности связаны с просчетами политического руководства.

Разочарование чекистов можно понять — на протяжении нескольких лет они пытались донести до партийных властей, что преобразования в стране зашли слишком далеко. «Через несколько дней будет ровно полвека, как началась война против Советского Союза. <…> И вы, наверное, сейчас читаете в газетах, как разведчики информировали тогда руководство страны о том, что делает противник, какая идет подготовка и что нашей стране грозит война. Как вы знаете, тогда к этому не прислушались. Очень боюсь, что пройдет какое-то время, и историки, изучая [сегодняшние] сообщения <…> Комитета госбезопасности, <…> будут поражаться тому, что мы многим вещам, очень серьезным, не придавали должного значения», — предупреждал Владимир Крючков депутатов Верховного совета СССР в июне 1991 года.

Руководство КГБ регулярно отправляло Горбачеву аналитические записки о положении дел в стране. Их посылали в секретных спецпакетах с сургучными печатями. По воспоминаниям одного из чекистов, когда осенью 1991 года в кабинете помощника Горбачева проводили обыск, в сейфе обнаружили более 400 невскрытых пакетов.

В итоге спецслужба стала заложником своей зависимости от партийного руководства — когда начался путч, она получала противоречивые указания от главы союзного КГБ Крючкова и от поддержавшего Ельцина главы российского КГБ Иваненко. Разозленные чекисты предпочли занять выжидательную позицию и ничего не делать.

Провал путча стал для всей корпорации чекистов самой большой катастрофой ХХ века. При этом многие из них понимали, что ситуацию в стране нужно менять, и были готовы на переход к рынку. «Лично я считал что лучше переболеть быстрее, чем растягивать процессы реформирования страны надолго. И выступал за то, что чем больше в стране богатых, тем богаче страна, ибо мы устали жить в государстве бедных», — вспоминал глава ленинградского УКГБ Анатолий Курков. Чего они совсем не могли принять, так это распада СССР и падения собственной значимости.

Патрушев никогда не рассказывал, как именно провел дни путча, но, скорее всего, он просто был на рабочем месте. Зато воспоминания оставил его начальник Анатолий Курков. Все три дня путча он сидел в своем кабинете в здании на Литейном проспекте и следил за тем, чтобы в городе не возникло беспорядков. После поражения путчистов он написал заявление об отставке, потому что испытывал «чувство моральной ответственности за произошедшее».