С делом Валленберга я впервые столкнулся еще в МВД, когда ко мне обратились из Посольства Швеции в СССР с просьбой разрешить членам международной комиссии ознакомиться с картотекой заключенных во Владимирской тюрьме, где, по некоторым сведениям, мог содержаться Валленберг.
В КГБ я запросил из архива все материалы по этому делу. Доложили, что есть около десятка документов, из которых пять неизвестны общественности. 4 сентября эти пять документов были переданы шведскому послу г-ну Бернеру. Среди них была копия донесения начальника политотдела 151-й стрелковой дивизии от 14 января 1945 года о том, что в Будапеште на улице Бенцур, 16 задержаны секретарь шведского посольства Рауль Валленберг и шофер его автомашины. Секретарь с шофером «помещены и охраняются». В журнале регистрации заключенных Внутренней тюрьмы была обнаружена запись кладовщика о приеме его вещей 6 февраля 1945 года. В тюремном деле немецкого ефрейтора Яна Лойда найдено было упоминание о том, что в свое время он сидел с Валленбергом на Лубянке; а в следственном деле служащего посольства Швеции в Будапеште Г. Томсона-Гроссгейма-Крысько — протокол его допроса о Валленберге. Наконец, было передано письмо зампреда КГБ Лунева в МИД от 1957 года, в котором согласовывался текст ответа на запрос МИД Венгрии относительно судьбы Вильяма Лангфельдера (шофера Валленберга). В письме говорилось, что все документы на Лангфельдера так же, как и на Валленберга, были уничтожены по распоряжению бывшего руководства МГБ.
Таковы были отправные точки дальнейшего поиска. Я дал указания о создании специальной внутриведомственной комиссии по расследованию этого дела, которая работала во взаимодействии с МИДом и МВД СССР, посольством Швеции в СССР, независимыми экспертами. До конца 1991 года были проведены три заседания советско-шведской комиссии, на которых согласовывался план поиска, шведской стороне передавались вновь найденные документы.
Работа проводилась по всем возможным направлениям. Проверялись все мыслимые фонды в архивах КГБ, в архиве военнопленных и интернированных Главархива СССР, в государственных и партийных архивах, в тюремных учетах, в списках пациентов психиатрических клиник, в книгах регистрации захоронений и кремирований. Был намечен список из более чем 20 лиц, которые могли в прежние годы хоть как-то соприкасаться с делом Валленберга. Каждому из них я лично подписал письмо с просьбой поделиться любой информацией о Валленберге, которая могла быть им известна, и с каждым из них беседовали члены советско-шведской комиссии в присутствии заместителя председателя Комитета по правам человека Верховного Совета РСФСР Николая Аржанникова. Проверялись показания свидетелей, утверждавших, что видели Валленберга в различных местах. Были сделаны запросы во все республиканские и областные управления КГБ с просьбой заняться поисками данных о Валленберге. Обрабатывались и проверялись все возможные версии, ничего не отвергалось и ничего не принималось на веру.