Первоначально все переговоры с террористами вел один из высоких военных чинов. Затем власти посчитали лучшим «смягчить» интонацию и отрядили для переговоров советника министра иностранных дел России Валентину Петренко.

25 декабря, в субботу, в 23.00 террористы внезапно решили взлететь. Пилот запросил у наземного д испетчера разрешение на три поворота по кругу над полем. «Добро» было дано. Но, сделав над полем один круг, вертолет вдруг выключил проблесковые огни и взял курс на Махачкалу. До этого террористы несколько раз поднимали вертолет в воздух, но, покружив над аэродромом, возвращались обратно — так они усыпляли бдительность властей. Теперь вертолет явно не намерен был возвращаться назад. Однако все получилось иначе.

Погода явно не благоприятствовала полету, и вскоре вертолет вернулся на аэродром. Во время этого полета в сторону Невинномысска и Махачкалы впервые был зафиксирован радиообмен между террористами и их сообщниками на земле.

К утру 26 декабря властям стало окончательно ясно, что террористы ни в какой Иран не собираются, а лишь выжидают момент, чтобы скрыться. К этому времени по согласованию с вице-премьером России Олегом Сосковцом, осуществлявшим из Москвы общее руководство операцией, Валентина Петренко была отстранена от переговоров, и все дальнейшие контакты были возложены на командующего ВВС Северо-Кавказского округа Владимира Михайлова.

Именно с этого момента преступникам был выставлен ультиматум: либо они возвращают последних заложников и улетают вместе с пилотами и деньгами, либо с их вылетом возникает большая проблема. Террористы раздумывали несколько часов, попивая водку «Распутин» (ее в вертолет по их требованию доставили утром). Наконец решение ими было принято.