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