После событий в Буденновске Генеральная прокуратура возбудила против Шамиля Басаева уголовное дело. ФСК объявило всероссийский розыск. Но Басаев так и не был арестован. 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 года «умиротворенный» Масхадов поручил своему врагу сформировать новое правительство.