3 июня 1995 г. в результате бомбардировки был разрушен дом дяди Басаева — Хасмагомеда Басаева в Ведено, в результате чего погибли 12 родственников Ш. Басаева, в том числе родная сестра — Зинаида, 1964 года рождения, и семеро детей (по другим данным, погибли 11 человек, в том числе якобы жена и дети Басаева). 14 июня 1995 г. под руководством Шамиля Басаева был совершен захват больницы с заложниками в г. Буденновске Ставропольского края с целью вынудить федеральные власти приостановить военные действия в Чечне и вступить в переговоры с дудаевцами. После телефонных переговоров с В. Черномырдиным, боевики Басаева покинули Буденновск и на границе Чечни отпустили заложников. Маршрут движения бандгруппы предположительно пролегал через Веденский район Новогрозненский, территории Дагестана, Ставропольского края. По рассказам Басаева, для операции в Буденновске он лично отбирал и готовил боевиков: «Моя поездка в Буденновск обошлась где-то в двадцать пять тысяч долларов. Правда, большая часть ушла на покупку КамАЗов и машины «Жигули» — пятнадцать тысяч долларов. А по дороге раздали тысяч восемь-девять. Когда мы захватили больницу, то все власти были в растерянности. По телевизору передают, что переговоры идут, деньги предлагают, а на самом деле ничего этого не было. Они два дня в растерянности были, даже боялись кого-нибудь прислать, только через сутки опомнились, и первый раз к нам чеченец из города пришел. В первый момент я удивился, когда Черномырдин мне позвонил. Но уже по тому, что он меня просил не поддаваться на провокации, не отвечать на них огнем, я понял, что он не мог управлять ситуацией. Премьер-министр, а власти у него было не очень много. Об операции Дудаев не знал. В тот момент у меня не было с ним связи второй месяц. Да даже если бы и была, то я не стал бы его посвящать в такие тонкости. Это мое правило» («Независимая газета»).
После событий в Буденновске Генеральная прокуратура возбудила против Шамиля Басаева уголовное дело. ФСК объявило всероссийский розыск. Но Басаев так и не был арестован. 21 июля 1995 года Басаеву «за особые заслуги перед Отечеством, проявленные мужество, самоотверженность по отражению российской агрессии» приказом Дудаева было присвоено звание «бригадного генерала» (досрочно). 18 Н. Н. Гродненский По другим данным, после операции в Буденновске весь личный состав вооруженного формирования Басаева был представлен Дудаевым к званию Герой Чечни. Трое заместителей Басаева получили орден «Честь нации». А сам Басаев — выговор за «невыполнение поставленной боевой задачи» (86). После события в Буденновске Басаев стал национальным героем Чечни, его авторитет в глазах чеченцев значительно вырос. Группировка Басаева пользовалась наибольшим авторитетом среди НВФ, а сам он все больше становился «сплачивающим фактором нации». Возглавляемый им отряд боевиков располагал значительными материальными средствами, включая БМП, установки «Град», ПЗРК «Стрела» и «Стингер». 19 июля 1995 г. в интервью заявил, что если население республики в ходе референдума выскажется за вхождение в состав РФ, он «не смирится и будет бороться и дальше». Летом — осенью 1995 года Басаев неоднократно угрожал правительству России новыми террористическими актами на территории РФ в случае, если не будут прекращены боевые действия и свернуты переговоры. В октябре 1995 года Шамиль Басаев взял на себя ответственность за обстрел российской бронегруппы 506-й мотострелковой бригады, в результате которой погибли 18 человек. На следующий день Аслан Масхадов опроверг это сообщение. О своей непричастности к этому нападению заявил и Ширвани Басаев, сообщивший, что в момент нападения он находился в расположении 506-й мотострелковой бригады и, наоборот, предлагал ее командиру организовать совместный отпор нападавшим. В декабре 1995 года был одним из руководителей штурма Грозного. В конце апреля 1996 г., после смерти Джохара Дудаева, Шамиль Басаев на совещании полевых командиров был избран «командующим боевыми формированиями Чеченской республики Ичкерия». В июне 1996 г. отряд Басаева насчитывал 300 человек. Один из руководителей штурма г. Грозный в августе 1996 года. С сентября 1996 года — председатель таможенного комитета в сформированном Яндарбиевым «коалиционном правительстве ЧРИ». В ноябре 1996 года отказался от предложенного поста вице-премьера Чечни в «коалиционном правительстве», пожелав остаться на должности командующего центральным фронтом, возглавляя одновременно таможенный комитет.