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 года отказался от предложенного поста вице-премьера Чечни в «коалиционном правительстве», пожелав остаться на должности командующего центральным фронтом, возглавляя одновременно таможенный комитет.
С апреля 1997 г. — первый вице-премьер правительства, с января 1998 — премьер-министр ЧРИ. С июля 1998 г. — заместитель министра обороны ЧРИ. 27 января 1997 г. на выборах президента Чеченской Республики занял второе рейтинговое место, проиграв Аслану Масхадову. Получил 23,7 % голосов избирателей (другие кандидаты — А. Масхадов — 59,7 %, 3. Яндарбиев — 10,2 %). На выборах баллотировался в паре с Вахой Ибрагимовым (советником Яндарбиева по внешнеполитическим вопросам). В 20-х числах февраля 1997 года на учредительном съезде так называемой Партии свободы Чеченской республики Ичкерии (ПС ЧРИ) был избран ее почетным председателем. В своем первом специальном заявлении партия осудила Р. Кутаева (Партия национальной независимости) за приглашение на торжество по случаю инаугурации А. Масхадова В. Черномырдина, А. Галазова (РСО-А), В. Кокова (КБР), которых обвинила в причастности к «развязыванию войны против чеченского народа». 10 июля 1997 года наступил кризис во взаимоотношениях с президентом Масхадовым, и Басаев подает в отставку «по состоянию здоровья». Однако здоровье вскоре пошло на поправку, что отразилось на занимаемых Басаевым «государственных» постах: в начале 1998 года «умиротворенный» Масхадов поручил своему врагу сформировать новое правительство.
После возобновления пребывания Басаева на посту «исполняющего обязанности премьер-министра» Чечни и состоявшихся рабочих контакТЪв с ним представителей правительства и Совета безопасности РФ, в американских общественно-политических кругах активно обсуждается вопрос о возможности его приезда в феврале-марте 1998 г. в США. Эксперты Госдепартамента отметили, что Басаев не включен американцами в официальные списки лиц, причастных к международному терроризму, а в перечне террористических организаций, опубликованном в Соединенных Штатах в октябре 1997 года, нет упоминания о чеченских вооруженных формированиях (данные на 01.01. 1998 г.). Согласно указу Масхадова от 15 января 1998 года, назначен первым вице-премьером Чечни. В результате позиции Ш. Басаева в руководстве Чечни усилились. Брат, Ширвани Басаев, стал руководителем Госкомитета ЧРИ по топливу и энергетике, то есть семья Басаевых полностью поставила под контроль нефтяной бизнес, убрав с дороги даже старых дудаевских выдвиженцев типа Яриханова и функционеров старой нефтяной мафии, представленной тейпами Мялхи и Орстхой-Цечой. В 1998 году возглавил Федерацию футбола Чечни. 10 августа 1999 года Басаев официально возглавил «вооруженные силы исламской Шуры». На него возложили обязанности «военного амира объединенными силами моджахедов Дагестана на период полного изгнания кафиров со священной дагестанской земли». Видимо, чувство реальности настолько изменило Басаеву, что он потребовал от мусульман, «состоящих на службе у кафиров», в трехдневный срок принести «товбу» (покаяние) и перейти на сторону борцов за веру — в противном случае им грозил арест. Руководство Шуры подтвердило: «В Дагестане начался джихад против неверных, который должны поддержать все правоверные мусульмане мира». В сентябре 1999 г. бандформирования под предводительством Шамиля Басаева и поддерживающих его чеченских полевых командиров вторглись на территорию Дагестана.
В феврале 2000 года был тяжело ранен, подорвавшись на мине при попытке покинуть Грозный. В мае 2000 года появилась информация, что Басаев умер. Оказалось, что Басаев жив, но находится в тяжелом состоянии — ему ампутировали ногу. В связи с этим в СМИ появились сообщения, что Басаев хочет договориться с федералами, так как он уверен, что его еще могут вылечить за границей, но выбраться из Чечни уже не может. В октябре 2000 года заявил о готовности отправить на Ближний Восток 150 своих «бойцов» (по его словам, к «священной войне за освобождение Иерусалима» были готовы присоединиться еще полторы тысячи чеченских боевиков).