В ноябре 2000 года лидер Соцпартии Украины Александр Мороз обнародовал аудиозаписи, сделанные в кабинете президента Украины Леонида Кучмы офицером охраны Николаем Мельниченко, на которых президент якобы говорит с главой СБУ Леонидом Деркачом и министром внутренних дел Юрием Кравченко о необходимости устранения журналиста. Кучма тогда утверждал, что записи сфабрикованы.
Бывший майор госохраны Украины Николай Мельниченко живет в США, где ему в апреле 2001 года было предоставлено политическое убежище. Он рассказал, что в бытность свою сотрудником спецслужб тайно записывал на аудиопленки разговоры в кабинете президента Украины Леонида Кучмы. На основании этих записей тогдашняя украинская оппозиция, возглавляемая Юлией Тимошенко и лидером социалистов Александром Морозом, обвинила президента Украины в причастности к убийству Георгия Гонгадзе. Записи Мельниченко также стали основанием для Госдепартамента США обвинить Украину ы в возможной причастности к продаже оружия Ираку.
В сентябре 2004 года МВД Украины признало факт уничтожения документов, которые могли бы подтвердить оперативную слежку за журналистом Георгием Гонгадзе перед его исчезновением. Документы были уничтожены в 2001 году, "поскольку истек их срок хранения, а некоторая часть была уничтожена раньше времени", - отметил Корниенко. Таким образом поручение Генпрокуратуры провести соответствующее расследование выполнить не удалось. Сотрудники службы наружного наблюдения утверждали, что слежки за Гонгадзе не было. В этой связи замминистра вынужден был констатировать, что однозначного ответа на данный вопрос нет.
Виктор Ющенко, который во время убийства журналиста занимал пост премьер-министра в правительстве Кучмы, вскоре после вступления в должность президента Украины пообещал, что на посту главы государства доведет это дело до "логического завершения.