В соответствии с брежневской политикой утешительных призов, которые раздавались высшим чинам номенклатуры, Семичастного задвинули на должность заместителя Председателя Совета Министров Украины, ответственного за физкультуру и спорт. Вернувшись в июне из больницы, Шелепин узнал, что и его понизили в должности, переведя с влиятельного поста секретаря ЦК, ответственного за органы контроля (в том числе и КГБ), на должность председателя Всесоюзного Центрального Совета Профсоюзов. Заняв свой новый просторный кабинет, Шелепин обнаружил, что у его предшественника Виктора Гришина в соседней комнате был «специально оборудованный массажный кабинет», как его культурно назвал Жорес Медведев. Шелепин был до глубины души возмущен, что, несмотря на свои прелюбодеяния в рабочее время, Гришин был с повышением переведен на должность первого секретаря Московского горкома партии, и начал распространять о нем всякого рода истории. «Брежнев был терпим в таких вопросах, если провинившийся был предан ему лично.»

Больше всех выиграл от устранения от дел Шелепина и снятия Семичастного Юрий Андропов, ставший новым председателем КГБ. Два протеже Брежнева — Семен Константинович Цвигун и Виктор Михайлович Чебриков (будущий председатель КГБ) — были назначены зампредами. Главная цель назначения Андропова заключалась в том, чтобы «приблизить КГБ к ЦК». Со времени возвращения из Будапешта в 1957 году Андропов возглавлял отдел ЦК по связям с коммунистическими и рабочими партиями соцстран. Он стал первым партийным чиновником, возглавившим КГБ, и первым председателем КГБ со времен Берии, входившим с состав Политбюро сначала как кандидат в члены, а с 1973 года как полноправный член Политбюро. Считалось, что назначение Андропова «ознаменовало завершение эволюции, продолжавшейся со смерти Сталина, — сближения партии и КГБ до такой степени, когда они действовали почти как две ветви одной и той же организации.» Но, хотя руководство партии добилось поставленной Брежневым задачи и установило надежное господство над КГБ, ему пришлось во многом принять «его мировоззрение». Андропову было суждено дольше всех своих предшественников проработать в должности председателя КГБ и добиться самых выдающихся политических успехов: в 1982 году он сменил Брежнева на посту Генерального секретаря.

Первым серьезным испытанием для Андропова на посту председателя КГБ стали события в Чехословакии. Зять Хрущева Алексей Аджубей, хотя и восхищался тем, как Андропов действовал во время Венгерской революции 1956 года, отметил, что события тех лет «наложили жестокий след на его воззрения» по поводу Восточной Европы. И все же годы, проведенные в Будапеште и та роль, которую сыграл «доморощенный сталинист» Ракоши в венгерских событиях, буквально спровоцировав революцию, убедили Андропова в необходимости гибкого подхода. Гордиевскому рассказывали, что вскоре после приезда в Москву Андропов заявил в Первом главном управлении: «Только гибкость позволит нам избежать повторения 1956 года.» К тому же заключению пришел в свое время и Хрущев, распорядившись, чтобы больше внимания уделялось национальным чувствам народов стран народной демократии. Он запретил КГБ шпионить в Восточной Европе и приказал работать в контакте с местными службами разведки и безопасности вместо того, чтобы пытаться диктовать им.

В середине шестидесятых более мягкая политика в отношении стран советского блока, похоже, начала приносить свои плоды. Руководитель Венгерской компартии Янош Кадар, пришедший к власти после революции 1956 года, пользовался в Центре хорошей репутацией, постоянно заверяя Москву в том, что его режим стабилен, а экономические реформы не носят подрывного характера. Он пользовался поддержкой АВХ и молодых выдвиженцев из Венгерской социалистической рабочей партии, которые верили, что чего-то можно добиться и при существующей системе.

Озабоченность Центра в связи с процессами в Восточной Европе, после того как Андропов стал председателем, в основном касалась Румынии. Георге Георгиу-Деж, генеральный секретарь ЦК Румынской компартии с 1944 года по 1954 год, готовился в тридцатые годы как агент НКВД. Главный советник КГБ в Бухаресте с 1949 по 1953 год Александр Сахаровский отмечал его рвение в ликвидации агентов титоизма и сионизма. Однако став начальником ПГУ, Сахаровский был не очень доволен националистическими тенденциями преемника Георгиу-Дежа Николае Чаушеску. Как и многие другие советские должностные лица, связанные с Восточной Европой, он критиковал решение Хрущева вывести советские войска из Румынии в 1958 году, считая его серьезным просчетом.

Как ни странно, гораздо меньше беспокойства вызывала Чехословакия. Старый специалист Центра по Чехословакии Анатолий Александрович Русаков позже рассказывал Гордиевскому, что в 1956 году ряд аналитиков ПГУ предсказали, что через несколько лет Прага последует контрреволюционному примеру Будапешта. Но когда предсказания не сбылись и Чехословакия стала весьма процветающей страной по стандартам советского блока, Центр успокоился, поверив в иллюзию безопасности. Когда в январе 1968 года на смену стареющему неосталинистскому Первому секретарю ЦК Чехословацкой компартии Антонину Новотному пришел сорокашестилетний Александр Дубчек, реакция в Центре и Кремле поначалу была положительной. В КГБ Дубчека называли «наш Саша». Когда в Чехословакии начались реформы, Одиннадцатый (восточноевропейский) отдел ПГУ сначала решил, что «нашим Сашей» хитро манипулируют «буржуазные элементы» в Чехословацкой компартии, но увидев, что Дубчек — одна из движущих сил «Пражской весны», и Кремль, и Центр почувствовали, что дело пахнет изменой. Очевидец, присутствовавший при разговоре Брежнева с Дубчеком после ввода советских войск в Чехословакию в августе, так описывал эту встречу: «Ведь я же тебе с самого начала хотел помочь в борьбе с Новотным, — сказал Брежнев Дубчеку. — Я верил тебе, защищал тебя, — корил он Дубчека. — Я говорил, что наш Саша — хороший товарищ. А ты нас так страшно подвел!» При этом голос Брежнева дрожал и прерывался: казалось, он вот-вот заплачет.»