4 июля 2003 года Генпрокуратура впервые заинтересовалась Леонидом Невзлиным, вызвав его для дачи свидетельских показаний по делу о хищении 20% акций ОАО "Апатит". 30 июля акционер ЮКОСа уехал в Израиль якобы для работы над диссертацией и 4 ноября получил там гражданство.
12 января 2004 года Генпрокуратура РФ заочно предъявила Леониду Невзлину обвинение в неуплате налогов на сумму 26,7 млн руб. и присвоении акций ОАО "Томскнефть" и ОАО "Ачинский НПЗ" на сумму $39 млн. В том же месяце он был объявлен в международный розыск, в Израиль направлен запрос об экстрадиции, который остался без ответа.
12 марта 2004 года Басманный суд выдал санкцию на арест банковских счетов 20 фигурантов дела ЮКОСа, в том числе и Леонида Невзлина. В Швейцарии были блокированы счета на сумму около $5 млрд. Позднее швейцарский суд отменил это решение из-за недостаточных оснований для ареста.
23 июля 2004 года Генпрокуратура РФ обвинила Невзлина в организации убийства супругов Гориных и трех покушениях, в том числе на Евгения Рыбина. Как утверждало следствие, во всех случаях он "давал прямые указания" сотруднику службы безопасности ЮКОСа Пичугину.
13 июля 2005 года Леонид Невзлин выступил в Вашингтоне перед членами Хельсинкской комиссии, призвав не допустить председательства РФ в G8, а также отказать ей во вступлении в ВТО. Накануне выступления Россия направила в США запрос об экстрадиции бизнесмена, но получила отказ.
20 июня 2006 года Генпрокуратура договорилась с израильским адвокатом Йорамом Мушкатом о представлении им интересов РФ по делу об экстрадиции Леонида Невзлина в Высшем суде справедливости Израиля. По мнению адвоката, господин Невзлин скрыл тот факт, что в России является фигурантом уголовного дела, и поэтому должен быть лишен гражданства. 24 мая 2007 года суд приступил к рассмотрению дела.
15 февраля 2008 года Генпрокуратура сообщила о завершении расследования уголовного дела Леонида Невзлина. По версии следствия, в 1998-2002 годах по его указанию были совершены убийства пятерых, а также покушения на шестерых человек.