15 января 2004 года Генпрокуратура заочно обвинила Леонида Невзлина в уклонении от уплаты налогов на 26,7 млн руб. и объявила его в федеральный и международный розыск.
27 января 2004 года первый замгенпрокурора Юрий Бирюков сообщил, что господину Невзлину добавлены обвинения в присвоении акций "Томскнефти" и Ачинского НПЗ на $39 млн.
В июле 2004 года Генпрокуратура обвинила Леонида Невзлина в организации убийства супругов-предпринимателей Сергея и Ольги Гориных и трех покушений: на начальника управления общественных связей мэрии Москвы экс-сотрудницу ЮКОСа Ольгу Костину, на бывшего начальника управления делами ЗАО "Роспром" Сергея Колесова и на управляющего компании East petroleum handelsgas GmbH Евгения Рыбина.
22 июня 2006 года 13 губернаторов регионов РФ разместили на сайте "Единой России" обращение к лидерам парламентских партий. В нем отмечено, что "на разжигание экстремистских настроений направлена и деятельность ряда спонсоров радикальной оппозиции — Невзлина, Гусинского, Березовского". В качестве примера роста экстремистских настроений было приведено убийство в Санкт-Петербурге таджикской девочки Хуршеды Султоновой.
17 августа 2006 года Мосгорсуд признал экс-сотрудника службы безопасности ЮКОСа Алексея Пичугина виновным в организации убийств директора торговой фирмы "Феникс" Валентины Корнеевой и мэра Нефтеюганска Владимира Петухова. В приговоре отмечено, что Пичугин выполнял приказы Леонида Невзлина.
В октябре 2006 года во время слушаний в суде области Тоскана (Италия) дела по экстрадиции в Россию экс-директора по стратегическому планированию и корпоративным финансам ЮКОСа Алексея Голубовича он обвинил Леонида Невзлина в том, что тот лишил его обещанных за работу 2,6% акций Group MENATEP и организовал два покушения на его семью.