16 сентября 2000 года в Киеве пропал учредитель оппозиционного интернет-издания "Украинская правда" Георгий Гонгадзе. 2 ноября в Таращанском лесу под Киевом нашли обезглавленный труп, который экспертиза признала телом журналиста.
28 ноября 2000 года лидер Соцпартии Украины Александр Мороз обнародовал "пленки Мельниченко" — аудиозаписи, на которых президент Леонид Кучма якобы приказал главе МВД Юрию Кравченко "разобраться" с журналистом. Вскоре оппозиция начала акцию "Украина без Кучмы", сам президент заявил, что ему "не в чем оправдываться".
22 октября 2003 года был задержан глава департамента внешнего наблюдения МВД Украины генерал-лейтенант Алексей Пукач. Его обвинили в уничтожении документов, свидетельствующих о слежке за журналистом. После вмешательства Леонида Кучмы, уволившего генпрокурора Святослава Пискуна, Пукач был отпущен под подписку о невыезде и скрылся. В декабре 2004 года генпрокурора Пискуна восстановили в должности, а Пукача объявили в розыск.
Требование раскрыть убийство стало одним из основных во время "оранжевой" революции. 1 марта 2005 года новый президент Виктор Ющенко объявил, что "дело Гонгадзе" раскрыто, а непосредственные участники убийства задержаны. 4 марта 2005 года на своей даче под Киевом был найден мертвым экс-глава МВД Юрий Кравченко, который должен был дать показания по делу. По официальной версии, он покончил с собой, дважды выстрелив в голову.
8 августа 2005 года объявлены имена подозреваемых. Ими оказались бывшие сотрудники МВД Валерий Костенко, Николай Протасов и Александр Попович. В ходе следствия они признались, что вместе с генералом Пукачом убили журналиста. 15 марта 2008 года их приговорили к лишению свободы на сроки от 12 до 13 лет.
21 июля 2009 года Алексей Пукач был задержан в селе Молочки Житомирской области. 28 июля по его наводке следователи нашли фрагменты черепа Георгия Гонгадзе. 14 сентября 2010 года Генпрокуратура сообщила, что приказ об убийстве журналиста отдал покойный генерал Юрий Кравченко.