Пройдя огнем и мечом Северный Иран, Джебе и Субедей обошли с юга Каспий и оказались на территории Закавказья. Началась ожесточенная борьба местных народов против захватчиков. По сообщению современника событий армянского историка Киракоса Гандзакеци (ок. 1203–1271), после того как грузинский царь Георгий IV Лаша (сын знаменитой царицы Тамары) «собрал… войско более многочисленное, чем в первый раз, и вознамерился дать бой неприятелю. А [татары], взяв с собой жен, детей и все свое имущество, намеревались пройти через Дербентские ворота в свою страну. Но мусульманское войско, находившееся в Дербенте, не пропустило их. Тогда они перевалили через Кавказские горы по неприступным местам, заваливая пропасти деревьями и камнями, имуществом своим, лошадьми и военным снаряжением, переправились и вернулись в свою страну. И звали их предводителя Саабата Багатур».

Дербент представлял собой мощный оборонительный комплекс, состоявший не только из цитадели Нарын-Кала и двойных городских стен, спускавшихся к морю, а также построенной еще персами тридцатикилометровой стены с укрепленными боевыми башнями. Пройти через Дербент имеющимися у монголо-татар силами было невозможно.

Ибн аль-Асир сообщает подробности: «Покончив с Шемахою, татары хотели пройти через Дербент, но не смогли и отправили посла к ширваншаху — дербентскому правителю, говоря ему, чтобы [он] отправил к ним посла для заключения мира. Он послал десять человек из лучших своих знатных людей, а они [монголы] взяли одного и убили, остальным же сказали: „Если вы укажете нам дорогу, по которой нам пройти, то вам будет пощада, а если не сделаете этого, мы убьем и вас“». Оставшиеся в живых девять посланцев вынуждены были провести завоевателей через труднопроходимое Ширванское ущелье на Северный Кавказ. По расчетам В.К. Романова, это было примерно летом — осенью 1222 г.

Здесь захватчикам противостояли аланы (предки современных осетин), вступившие в союз с половцами (кипчаками), уже более столетия кочевавшими в местных степях. Войска Джебе и Субедея несколько раз сразились здесь с алано-половецким военным альянсом. Не сумев добиться победы, монголо-тата-ры пошли на хитрость и смогли разъединить вчерашних союзников. По Ибн аль-Асиру, «татары послали к кипчакам сказать: „Мы и вы одного рода, а эти аланы не из ваших, так что вам нечего помогать им; вера ваша не похожа на их веру, и мы обещаем вам, что не нападем на вас, а принесем вам денег и одежд сколько хотите; оставьте нас с ними“. Уладилось дело между ними на деньгах, на одеждах и пр.; они [татары] действительно принесли им то, что было выговорено, и кипчаки оставили их [алан]. Тогда татары напали на алан, произвели между ними избиение, бесчинствовали, грабили, забрали пленных и пошли на кипчаков, которые спокойно разошлись на основании мира, заключенного между ними, и узнали о них только тогда, когда те нагрянули на них и вторглись в землю их. Тут стали они [татары] нападать на них раз за разом и отобрали у них вдвое против того, что [сами] им принесли. Услышав эту весть, жившие вдали кипчаки бежали без всякого боя и удалились; одни укрылись в болотах, другие в горах, а иные ушли в страну русских».

Уточнить маршруты передвижения монголо-татарских войск через Северный Кавказ позволяют данные археологии. Места возможной локализации сражений алано-половецких войск с отрядами Джебе и Субедея ныне определяются на правобережье реки Сунжи, на отрезке от места ее впадения в Терек до современного Гудермеса. Это предположение подкрепляется многочисленными случайными находками в этом районе предметов вооружения.

Дальнейшее движение войск Джебе и Субедея от места слияния Сунжи и Терека восстанавливается предположительно. Начавшаяся погоня за отошедшими половцами могла осуществляться несколькими отрядами, что косвенно подтверждается Ибн аль-Асиром, рассказывающим, что «стали они [татары] нападать на них раз за разом».