16 апреля 1996 года Гелаев вместе с Хаттабом устроил засаду у села Ярыш-Марды в Аргунском ущелье, в которую попала колонна федеральных войск МВО. Погибли 76, ранены 54 человека.
6 марта 2000 года с отрядом из 1000 боевиков Гелаев захватил село Комсомольское. К 14 марта боевики были разгромлены, Гелаев ушел из окружения. В боях погибло около 50 военнослужащих федеральных сил, более 300 получили ранения.29 марта 2000 года в засаду боевиков отряда Гелаева возле поселка Джаной-Ведено попали пермский ОМОН и две колонны внутренних войск. 32 милиционера погибли на месте, 11 захвачены в плен и казнены.
8 октября 2001 года по приказу Гелаева в Кодорском ущелье сбит вертолет Ми-8 с сотрудниками миссии ООН. Погибли три члена экипажа и пять пассажиров, включая заместителя главы миссии ООН по наблюдению в Грузии подполковника Ласло Торока.
10 ноября 2001 года боевики Гелаева Руслан Чахкиев и Мовсар Темирбиев устроили взрыв на рынке Фаллой во Владикавказе. 5 человек погибли, 62 получили ранения. 28 апреля 2002 года они же заложили бомбу на центральном рынке Владикавказа. Семь человек погибли, пять получили ранения. 1 октября 2002 года боевики задержаны и 14 июля 2003 года приговорены к 24 и 18 годам лишения свободы соответственно.
20 сентября 2002 года 200 боевиков под командованием Гелаева вторглись в село Тарское Пригородного района Ингушетии, расстреляли двух российских военнослужащих и взяли в заложники четырех местных жителей.
26 сентября 2002 года боевики под командованием Гелаева напали на ингушское село Галашки. В ходе боев, продолжавшихся двое суток, подразделения 58-й армии и МВД Ингушетии потеряли 14 военнослужащих и вертолет Ми-24.
В начале октября 2002 года Гелаев со своим отрядом прорвался из Панкисского ущелья Грузии в Чечню через Ингушетию. В ходе боев погибло около 20 российских военных.
15 декабря 2003 года банда во главе с Гелаевым совершила нападение на ряд сел Цунтинского района Дагестана. Девять пограничников попали в засаду и были убиты.