20 декабря 2003 года бойцами батальона "Восток" ликвидирован полевой командир Мовсар Теймасханов и часть его бандформирования. Семеро боевиков захвачены в плен.
В начале 2004 года бойцы "Востока" уничтожили в Веденском районе Чечни Абу аль-Валида — преемника арабского террориста Хаттаба.
В апреле 2004 года "Восток" в Веденском районе уничтожил бригадного генерала Махрама Саидова по кличке Рыжий.
18 августа 2004 года министр обороны РФ Сергей Иванов встретился в Ханкале с начальниками "Востока" и "Запада" Сулимом Ямадаевым и Саидмагомедом Какиевым и заявил, что батальоны "успешно выполняют задачи по уничтожению боевиков в Чеченской республике".
25-11 сентября 2004 года "Восток" провел операцию по ликвидации отряда боевиков, готовивших крупный теракт на территории Дагестана. Было обезврежено около 50 членов группировки, из них 38 ликвидировано.
9 ноября 2004 года в Гудермесе был открыт мемориальный комплекс и зажжен вечный огонь в честь погибших бойцов "Востока" и их первого командира Джабраила Ямадаева. В церемонии участвовало руководство республики.
4 июня 2005 года бойцы "Востока" провели зачистку в станице Бороздиновской Шелковского района Чечни, в результате которой убит 1 человек, 11 похищены, сожжено 4 дома. В результате жители селения покинули станицу и ушли в Дагестан. Для урегулирования ситуации понадобилось вмешательство полпреда Дмитрия Казака. 26 октября 2005 года командир роты батальона Мухади Азиев получил условный срок за превышение полномочий.
22 июня 2005 года президент Чечни Алу Алханов подверг критике несогласованные действия батальонов в борьбе с преступностью: "Захотел батальон 'Восток' — провел мероприятие, захотел батальон 'Запад' — тоже провел мероприятие. Так в Чечне порядка не будет".
17 октября 2005 года бойцы батальона "Запад" совместно с сотрудниками УФСБ РФ по Чечне в Грозном задержали эмира Салеха Джахонтова и двух членов его бандгруппы, которые ранее участвовали в нападении на селение Рошни-Чу.
8 февраля 2006 года "Восток" понес самые крупные небоевые потери за всю историю своего существования. При взрыве бытового газа в казарме батальона в Курчалое погибли 13 человек, 20 получили ранения. Первоначально рассматривалась версия теракта, но вскоре она отпала.
21 февраля 2006 года военнослужащие батальона "Запад" вступили в столкновение с боевиками в Старопромысловском районе Чечни. Задержать никого не удалось, в руки военных попало оружие и 2 кг ртути, которой бандиты намеревались отравить воду в водозаборе.