Нерешительность федерального командования способствовала не только укреплению дудаевской обороны в Первомайском, но и снижению морально-боевого духа российских войск, располагавшихся на подступах к этому населенному пункту. Солдаты были слишком голодными и замерзшими, чтобы думать о Радуеве. С каждым днем и часом они все больше думали о еде и тепле. Руководители операции нисколько не заботились о своих подчиненных – десантникам за трое суток ни разу не доставили горячей пищи, кончились сухие пайки. На третьи сутки солдаты и спецназовцы начали охоту на разбежавшихся из Первомайского коров, коз, гусей, кур. С наступлением темноты оголодавшие воины из подразделений, менее удачливых в охоте, отправлялись к ближайшим селениям, покинутым жителями, и тащили оттуда все, что можно съесть или использовать в качестве одеяла. «Деды» из махачкалинского батальона внутренних войск быстро нашли общий язык с мужчинами, оставшимися охранять свои дома, и выпивали вместе с ними «за победу над Радуевым». Дисциплина в рядах федеральных сил стремительно падала.
С утра 15 января по решению командования федеральные войска начали штурм Первомайского. Он развивался крайне медленно – никто не хотел выходить на открытую местность, все ограничивались перестрелкой с больших расстояний. К 16 часам стало ясно, что операцию не удастся завершить в течение светового дня, в течение которого лишь немногим удалось достичь окраин Первомайского. Боевики же смогли организованно отойти в центральную и южную части села, где оказали упорное сопротивление. В очередной раз расписавшись в своем бессилии, федеральное командование поздно вечером 15 января прекратило штурм Первомайского и отвело войска на исходные рубежи для перегруппировки.
Штурм Первомайского проводился одновременно с попыткой склонить дудаевцев к сдаче путем переговоров. Для их ведения в район боевых действий прибыли директор Федеральной службы безопасности Российской Федерации Михаил Барсуков, министр внутренних дел России Анатолий Куликов и министр внутренних дел Дагестана Магомед Абдуразанов. Однако С. Радуев от капитуляции отказался.
В это же время состоялся радиоперехват разговора террористов со штабом Дудаева. Чеченский главарь предупредил своего подчиненного: «Не ведите долгих переговоров, каждое слово, каждая интонация – против вас. Подготовьте милиционеров к расстрелу и предупредите их об этом. Даже можно некоторых расстрелять… Держите жесткую позицию. К вам идут на помощь… Считайте себя смертниками. Готовьтесь предстать перед Аллахом. Забудьте обо всем земном, тогда вам будет легче. Исходите из самого худшего».
После расшифровки этого радиоперехвата бесцельность ожидания переговоров стала очевидной. К исходу дня в окрестностях Первомайского были сосредоточены значительные силы федеральных войск. В их составе находилось более двух тысяч человек личного состава, танк, 80 единиц бронетехники, 32 орудия и миномета, 3 установки «Град», 16 огнеметов. По расчетам, этих сил было вполне достаточно, чтобы не допустить прорыва террористов и обеспечить их быстрое уничтожение в населенном пункте.
На следующий день в 11 часов по Первомайскому был нанесен мощный огневой удар боевыми вертолетами. Следом подразделения федеральных сил атаковали чеченский блокпост, расположенный на южной окраине села. Хотя данный блокпост и был взят, но и в этот день разгромить дудаевцев в Первомайском также не удалось. Слабым утешением для федералов стало освобождение четырех десятков заложников, при том, что в руках террористов оставалось еще более сотни несчастных.
Сами террористы действовали более умело. Среди ночи 18 января группа террористов открыла огонь с южной и юго-западной окраин Первомайского. В это же время со стороны Советского в тыл российским войскам ударил отряд дудаевцев, пришедший из Чечни через Нижний Герзель. Завязался огневой бой, который федеральное командование приняло за подготовку прорыва террористов. Все силы были брошены на угрожаемое направление.
Реально же прорыв готовился с северо-западной стороны населенного пункта. Там в три часа ночи другая группа чеченцев, пустив впереди заложников, внезапно атаковала растерявшихся от неожиданности солдат. В результате скоротечного рукопашного боя около 40 чеченцев во главе с Салманом Радуевым прорвали слабое кольцо окружения. Они ушли на территорию Чечни, уводя с собой группу заложников. Большая их часть была возвращена только 24 января, и опять‑таки за определеные уступки со стороны федерального руководства.
Настало время подвести итоги трагических событий, произошедших в Первомайском. По словам российского президента, в этом населенном пункте было уничтожено 153 и пленено 30 террористов. Потери федеральных войск при штурме станицы составили 26 человек убитыми и 93 ранеными. О потерях среди заложников и местных жителей, как обычно, не сообщалось.