21 января 1999 года в российских СМИ впервые появились слухи о смерти Шамиля Басаева, полученные от анонимных источников "на достаточно высоком уровне". Сообщалось, что террорист был убит во время столкновений между сторонниками Аслана Масхадова и ваххабитами в Урус-Мартане.
22 мая 2000 года анонимные источники в ОГВ сообщили, что Шамиль Басаев умер от заражения крови. Гангрена якобы была вызвана ранением, полученным при прорыве из Грозного 2 февраля 2000 года и ампутацией ноги в полевых условиях. Официально информация не подтверждалась, а помощник президента Сергей Ястржембский посчитал ее "информационной уткой". В интервью "Кавказ-центру" Басаев назвал слухи о своей смерти "всплесками информационной шизофрении".
19 июня 2000 года Агентство военных новостей передало, что накануне вертолеты Ми-24 ракетным ударом уничтожили конную группу боевиков во главе с "безногим человеком, похожим на Шамиля Басаева", в горной местности между населенными пунктами Ведено и Дарго. Отмечалось, что смерть террориста подтверждена "по одному из агентурных каналов". В тот же день Сергей Ястржембский объявил, что 18 июня в Чечне стояла нелетная погода, поэтому "авиация не летала и не могла уничтожить никакие конные группы".
22 июля 2000 года агентство ИТАР-ТАСС со ссылкой на "офицера армейской разведки в Моздоке Дмитрия К." сообщило о "плачевном" состоянии Шамиля Басаева. Отмечалось, что полевой командир Хаттаб "под страхом смерти" запретил всем боевикам распространяться о здоровье Басаева.
20 августа 2001 года анонимные представители УВД Чечни сообщили интернет-изданию Strana.ru, что "Басаев потерял рассудок, абсолютно не контролирует себя, почти разучился говорить" и, вероятно, скоро умрет. Его мозг якобы пострадал из-за заражения крови, вызванного ранением в феврале 2000 года. 23 августа один из сообщников Басаева, Ризван Читигов, заявил в интервью "Комсомольской правде", что Басаев "жив-здоров и чувствует себя прекрасно".
30 апреля 2002 года начальник Генштаба Анатолий Квашнин заявил, что Шамиль Басаев, вероятно, погиб в результате спецоперации в марте--апреле того же года. Телекомпания РТР со ссылкой на собственные источники добавила, что террорист скончался от ран в период с 7 по 10 марта.
22 мая 2002 года командующий СКВО Геннадий Трошев заявил, что Шамиль Басаев погиб под артобстрелом. Генерал отметил, что фактических доказательств этого нет и, возможно, не будет, так как боевик "погиб от разрыва снаряда и найти части его тела не представляется возможным". Информация, по словам Геннадия Трошева, была получена от пленного, который в момент взрыва был рядом с Басаевым. 24 мая того же года российский правозащитник Александр Подрабинек сообщил, что смог связаться с Шамилем Басаевым и взять у него интервью.