21 января 1999 года российские СМИ со ссылкой на источники "на достаточно высоком уровне" сообщили, что Шамиль Басаев погиб в бою между сторонниками Аслана Масхадова и ваххабитами в Урус-Мартане. Однако 7 февраля боевик выступил в эфире ичкерийского телевидения.
22 мая 2000 года анонимные источники в объединенной группировке войск на Северном Кавказе заявили, что Басаев умер от заражения крови, вызванного полученным при прорыве из Грозного ранением и ампутацией ноги в полевых условиях. Через несколько часов в интервью сайту "Кавказ-центр" боевик назвал эти слухи "всплесками информационной шизофрении".
19 июня 2000 года Агентство военных новостей передало, что накануне вертолеты Ми-24 уничтожили в Чечне конную группу во главе с "безногим человеком, похожим на Шамиля Басаева". Через несколько часов помощник президента Сергей Ястржембский объявил, что 18 июня в Чечне стояла нелетная погода, поэтому "авиация не летала и не могла уничтожить никакие конные группы".
30 апреля 2002 года начальник Генштаба Анатолий Квашнин заявил, что Шамиль Басаев, вероятно, погиб в результате спецоперации в марте-апреле того же года. Телекомпания РТР со ссылкой на собственные источники добавила, что он скончался от ран в период с 7 по 10 марта. 22 мая командующий СКВО Геннадий Трошев подтвердил, что боевик погиб под арт-обстрелом и "найти части его тела не представляется возможным". 24 мая правозащитник Александр Подрабинек сообщил, что смог связаться с Шамилем Басаевым.
3 февраля 2005 года зампред службы госбезопасности Абхазии Юрий Ашуба заявил о возможной смерти террориста, приведя две версии: гибель в ходе разборок с арабскими наемниками или обострение хронического заболевания почек. 8 февраля "Кавказ-центр" разместил видеоинтервью с Шамилем Басаевым, записанное 6 февраля.
13 октября 2005 года грозненская газета "Чеченское общество" со ссылкой на источник в УФСБ Чечни сообщила, что Шамиль Басаев был убит во время нападения боевиков на Нальчик при попытке захвата городского аэропорта. 16 октября террорист через "Кавказ-центр" раскрыл детали рейда в Кабардино-Балкарию.