15 января 1996 г. начался штурм села федеральными войсками силами частей СН (осн «Витязь», СОБРы, части 22-й обрсн и др.) Над селом появились десять вертолетов, которые нанесли по захваченному бандитами блокпосту ракетный удар. Одновременно последовал артиллерийский залп из 85-мм орудий (которые в подобной обстановке были признаны неэффективными). В результате несколько снарядов, перелетев село, попали в расположение собственных войск. Ко второй половине дня большая часть Первомайского была занята федеральными силами. Но большие потери — 13 раненых и 7 убитых — заставили их вновь вернуться на исходные позиции. Солдаты ночевали на броне, промерзшие и голодные
16 января штурм был вновь повторен. Управление войсками было частично потеряно, но бандиты были вынуждены выйти под пули. Это произошло в результате непрекращавшегося массированного обстрела и в не меньшей степени благодаря распространенной информации, что «заложники уже мертвы». В результате повторного штурма потери составили 15 человек убитыми и ранеными. Разделившиеся на три группы, радуевцы попытались прорваться. г Одна из групп наткнулась на минное поле, где потеряла 43 человека. 30 боевиков отступили назад и на следующий день сдались властям. Еще 9 человек были арестованы в небольшом лесочке перед Тереком (двое из них скончались от ран).
Артиллерия — батарея реактивных пусковых установок БМ-21 «Град» и батарея 122-мм гаубиц Д-30 прибыла к атакующим лишь к исходу дня 16 января. Ночь с 16-го на 17-е прошла, как и предыдущая: небо над Первомайским подсвечивали САБами, которые сбрасывали самолеты с большой высоты. Утром 17 января в 8.00 поступила команда оставить позиции и отойти на 500 метров, дабы не пострадать от огня артиллерии. Авиация вновь нанесла ракетный удар по Первомайскому. После чего началась «зачистка» села «Альфой». В ходе ее двое «альфовцев» погибли от случайной очереди своего же товарища. В этот же день группа боевиков в районе села Советское атаковала внешнее кольцо окружения под Первомайским. Около полуночи боевики общей численностью до 250 человек прорвались на участке, который удерживал отряд спецназа 22-й обрСпН численностью 45–50 человек. Боевики ударили точно в стык между спецназом и дагестанским ОМОНом. Разведчики дрались отчаянно, сдерживая пятикратно превосходящего противника, которому к тому же нечего было терять. Их героические усилия никто не поддержал ни огнем ни маневром. Да и кому было поддерживать, если боевой порядок операции не предполагал ни создания бронегруппы, ни резерва, а для того, чтобы осуществить быструю перегруппировку, надо хотя бы находиться в трезвом рассудке. При прорыве бандитов войска Министерства обороны потеряли убитыми 5 человек. В целом же, по официальным сводкам, в Кизляре и Первомайском их потери составил 29 человек. А потери органов внутренних войск — 27 человек. Когда заместителю Куликова генерал-лейтенанту Голубцу доложили о прорыве, он, по отзывам очевидцев, был до такой степени пьян, что единственное распоряжение, которое смог отдать, звучало примерно так: «Доставить их (боевиков) мне сюда!» Лишь около 11.00 18 января после удара «Града» и гаубиц спецподразделения ФС пошли в новую атаку и к 15.00 овладели населенным пунктом. К этому времени основные силы чеченцев давно прорвались из Первомайского
Большинство найденных трупов чеченцев было обнаружено с оружием в руках, т. е. все говорило, что это именно бандиты, а не заложники. Во время осмотра села было установлено, что для обороны радуевцы использовали мины и снаряды российского производства, датированные 1995 годом. Согласно одной из версий, их им продавали командиры блокпостов. На месте ночного боя сотрудниками прокуратуры была найдена втоптанная в грязь карта-километровка с нанесенным на нее точным указанием расположения федеральных сил вокруг села
В общей сложности в Кизляре и Первомайском погибло свыше 65 милиционеров и жителей. В Кизляре бандиты расстреляли около 34 человек, а остальные (включая омоновцев) 31 погибли в Первомайском. О потерях банды Радуева сообщил начальник штаба дудаевцев Аслан Масхадов. Согласно его данным, они составили 53 погибших боевика. А вот как выглядели события в Первомайском со слов еще одного очевидца и непосредственного участника: «Когда поступило сообщение о захвате заложников в Кизляре, на Ханкале была создана войсковая группа, в которую вошли мой отряд и отряд из 7-й воздушно-десантной дивизии. По первоначальному плану в момент пересечения границы Чечни автобусов с террористами по ним должен быть нанесен удар вертолетами. Колонна остановится, мы высадимся, обезвредим бандитов и освободим заложников. На все не более 40 минут.