Назначением на должность первого начальника Управления Д Агаянц был обязан своим успехам в подготовке серии поддельных мемуаров. Среди этих работ были «воспоминания» генерала Власова «Я выбрал виселицу», «Моя карьера в высшем советском командовании» Ивана Крылова и опубликованная в еженедельнике «Карфур» переписка Сталина и Тито, где Тито якобы признается в своих троцкистских симпатиях. На самом деле автором большинства этих работ был, по всей видимости, Григорий Беседовский, бывший советский дипломат, который в период между двумя мировыми войнами обосновался в Париже и позже стал сотрудничать с НКВД. Фальшивки Беседовского, среди которых были и две книги о Сталине, написанные его несуществующим племянником, были настолько мастерски сделаны, что ввели в заблуждение даже такого видного советского ученого, как Е.Х. Карр, который в 1955 году написал предисловие к «Журнальным заметкам», якобы написанным бывшим наркомом иностранных дел Максимом Литвиновым. Некоторые фальшивки и поддельные информационные сообщения Службы А, с которыми Гордиевский сталкивался в семидесятых и восьмидесятых годах, были сработаны грубо по сравнению с теми произведениями.
Одним из первых объектов деятельности Агаянца, после того как в 1959 году он возглавил Управление Д, стала Западная Германия, которую КГБ пытался изобразить оплотом неонацизма. Чтобы опробовать одно из «активных действий» прежде, чем использовать его в Германии, Агаянц послал группу своих сотрудников в деревню километрах в пятидесяти от Москвы, где они под покровом темноты должны были намалевать свастики, антисемитские лозунги и опрокинуть надгробья. Осведомители КГБ в деревне сообщили, что, хотя инцидент и встревожил многих жителей деревни, он спровоцировал небольшую группу местных антисемитов на подобные действия, направленные против евреев. Зимой 1959—1960 гг. Агаянц с большим успехом применил ту же тактику в ФРГ. На Запад были направлены восточногерманские агенты, которые получили задание осквернять еврейские памятники, синагоги, магазинчики и малевать на стенах антисемитские лозунги. Начатая КГБ кампания была стихийно подхвачена местными хулиганами и неонацистами. С Рождества 1959 года до середины февраля 1960 года западногерманские власти зарегистрировали 833 антисемитские акции. Затем кампания внезапно прекратилась, но она успела серьезно скомпрометировать ФРГ в глазах международной общественности. Западногерманским политическим и религиозным деятелям пришлось испить горькую чашу позора. Общую реакцию зарубежной прессы на те события лучше всего передает заголовок статьи в «Нью-Йорк геральд трибюн» — «Бонн не в состоянии изжить яд нацизма».
В мае 1959 года Шелепин организовал в Москве крупнейшую со времени создания ЧК конференцию по вопросам разведывательной деятельности, на которой были обсуждены приоритетные задачи КГБ. В конференции приняли участие две тысячи сотрудников КГБ, представитель от Политбюро Алексей Илларионович Кириченко, члены Центрального Комитета партии и представители министерств обороны и внутренних дел. Шелепин выступил с комплексной программой мобилизации усилий разведслужб всех стран советского блока на достижение долгосрочных целей советской политики и устранение угрозы со стороны США, их союзников по НАТО и Японии. Управлению Д предписывалось согласовывать свою программу «активных действий» с Международным отделом ЦК и госаппаратом.
Несмотря на свою довольно изощренную программу «активных действий», Шелепин не собирался отказываться от более радикальных «специальных операций» за рубежом. При Серове Тринадцатый отдел ПГУ, занимавшийся «мокрыми делами», был замешан в нескольких публичных скандалах. После неудачи во Франкфурте, когда не удалось ликвидировать Георгия Околовича, руководителя эмигрантской организации «Народно-трудовой союз» (НТО, а непосредственный исполнитель акции сотрудник КГБ Николай Хохлов бежал на Запад в 1954 году, Тринадцатый отдел нанял в 1955 году профессионального убийцу — немца Вольфганга Вильдпретта для ликвидации президента НТС Владимира Поремского. Но, как и Хохлов, Вильдпретт в последний момент передумал и сообщил обо всем западногерманской полиции. Неудачей закончилась и попытка Тринадцатого отдела отравить Хохлова радиоактивным таллием в сентябре 1957 года (этот метод был выбран в надежде, что следы таллия не будут обнаружены при вскрытии). Вслед за неудачами последовали успешные операции по ликвидации двух лидеров украинской эмиграции в Западной Германии — главного идеолога НТС Льва Ребета в октябре 1957 года и руководителя Организации украинских националистов (ОУН) Степана Бандеры в октябре 1959 года. Эти операции убедили Шелепина и Хрущева, с санкции которого они и проводились, что убийства отдельных лиц по-прежнему являются необходимым элементом деятельности КГБ за рубежом.
Исполнителем обеих акций Тринадцатого управления был Богдан Сташинский, которому было всего 25 лет, когда он убил Ребета. Сташинский готовил операции в городке КГБ в Карлсхорсте. Орудие убийства было разработано в оружейной лаборатории КГБ («хозяйство Железного») и представляло собой газовый пистолет, который стрелял струей ядовитого газа из разбиваемой ампулы с цианистым калием. При попадании газ вызывал остановку сердца. Тринадцатый отдел правильно рассчитал, что ничего не подозревающий патологоанатом, скорее всего, напишет в заключение, что причиной смерти явилась сердечная недостаточность. Сташинский сначала испытал действие пистолета на собаке: он отвел ее в лес неподалеку от Карлсхорста, привязал к дереву и выстрелил. Собака забилась в конвульсиях и через несколько секунд умерла. Убедившись таким образом в безотказности своего оружия, Сташинский убил и Ребета, и Бандеру, подкараулив их в темном подъезде. В декабре 1959 года Сташинского вызвали в Московский центр, где Шелепин в торжественной обстановке вручил ему орден Красного Знамени и зачитал приказ о награждении, в котором говорилось, что награда вручается «за успешное выполнение особо важного задания правительства». Сташинскому сообщили, что он направляется на курсы, где продолжит изучение немецкого языка и выучит английский, после чего он три или пять лет проведет на Западе, выполняя новые «задания» того же характера. «Работа вас ждет нелегкая, но почетная,» — сказал ему тогда Шелепин.
