Своё имя казачье подразделение получило в результате дискуссии, разгоревшейся на Совете атаманов ТКВ, ещё до начала своего формирования — в январе 1996 года. Было предложено назвать батальон Карауловским — в честь первого выборного терского войскового атамана, расстрелянного в декабре 1917 года революционными солдатами здесь же, на станции Прохладной, но большинством голосов атаманы утвердили второе предложение, высказанное одним из них — быть батальону Ермоловским. Имя знаменитого генерала — покорителя Кавказа, присвоенное создаваемому казачьему подразделению, явилось и проявлением исторической преемственности — ещё в 1904 году по Высочайшему повелению Алексей Петрович Ермолов был определён вечным шефом Терского казачьего войска.

В конце февраля на базе в/ч 01860 в Моздоке началось формирование казачьей усиленной роты (160 человек), приданной Ермоловскому батальону в 20-х числах марта под Ачхой-Мартаном.

При комплектовании батальона применялась упрощенная система — кандидату в военнослужащие для оформления личного дела в военном комиссариате по месту жительства не требовалось даже прохождения медицинской комиссии. Необходимо было только представить справку из милиции, подтверждающую, что данный человек не находится под следствием. Отменялись и возрастные ограничения. Так одному из старейших казаков батальона В.С.Метликину в день первого боя 8 марта 1996 года исполнилось 55 лет.

При комплектовании взводов учитывался старый казачий принцип землячества. Так во 2-ой роте Ермоловского батальона 1-ый взвод состоял в основном из казаков Минераловодского отдела, 2-ой взвод — Прохладненского отдела, 3-й взвод — Павловского отдела. Командирами взводов были не офицеры Российской Армии, но свои «полевые командиры» (походные атаманы). «Земляческая» спайка позволяла подразделениям наиболее эффективно выполнять поставленные командованием боевые задачи.