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

Следующие четыре дня противостояния обе стороны активно готовились к боевым действиям. Боевики силами заложников укрепляли село. Федеральные войска подтягивали артиллерию, дополнительные подразделения, проводили разведку позиций. Таким образом под Первомайским была сосредоточена разновидовая группировка войск общей численностью 2 500 человек, 32 орудия и миномета, 16 огнеметов, 10 гранатометов, 3 установки РСЗО «Град», 54 БМП, 22 БТР, 4 БРДМ, несколько танков и боевых вертолетов.

У Радуева было около 300 боевиков, свыше 100 заложников, 82-мм минометы, вывезенные из Кизляра на грузовиках с телами убитых, а также большое количество пулеметов, гранатометов, огнеметов и иного оружия и боеприпасов. Боевики пополнили свой арсенал за счет разоружения блокпоста новосибирского ОМОНа.

Террористы расстреляли 14 января двух пришедших к ним на переговоры дагестанских старейшин и 6 милиционеров-заложников, после чего было принято решение провести штурм с применением вертолетов, танков и БТРов. Общее командование федеральных сил осуществлял Виктор Зорин, первый заместитель директора ФСБ Михаила Барсукова.

Утром 15 января после незначительной артиллерийской подготовки и авиационной поддержки девять штурмовых групп: отряд специального назначения «Витязь», специальные отряды быстрого реагирования СОБР и подразделения 22-й отдельной бригады специального назначения ГРУ ГШ - пошли на штурм. Во втором эшелоне в полной готовности к штурму строений, в которых могли находиться заложники, шли штурмовые группы Управления «Альфа» и бойцы ФСБ.

К 13 часам «витязи», преодолев канал, уничтожили первую линию обороны боевиков на окраине села и ворвались в юго-восточный квартал. Остальные, наткнувшись на ожесточенное сопротивление в районе моста и кладбища, вынуждены были остановиться. Через два часа, понеся потери, остановился и «Витязь». С наступлением сумерек всем подразделениям было приказано отойти на исходные позиции.

В турецком порту Трабзон, террористами во главе с Токджаном, воевавшим, по его утверждению, в батальоне Басаева, 16 января был захвачен паром «Авразия» с преимущественно российскими пассажирами на борту. Требованиями террористов были снятие блокады села Первомайское и вывод федеральных войск с Северного Кавказа. Утром 17 января в близлежащее от Первомайского село Советское со стороны Чечни прорвалась небольшая группа боевиков и уничтожила автомобиль УАЗ с дагестанскими омоновцами.

В ночь на 19 января основным силам боевиков, включая Радуева и Турпал-Али Атгериева, удалось вырваться из окружения и вернуться в Чечню. Общее число выдвинувшихся боевиков - 256 человек, выехавших на 7 грузовиках КамАЗ. Во время ночного прорыва террористов из Первомайского, приняв бой, погибли 2 солдата и 3 офицера 22-й отдельной бригады специального назначения. Прорыв шел через их позиции. Погиб также находившийся на их позициях начальник разведки 58-й армии полковник Александр Стыцина.