Вновь трогается в путь славный Автандил, «много встречных за сто суток расспросил он по базарам, / Но о деве не услышал, лишь потратил время даром», покуда не встретил караван торговцев из Багдада, предводителем которого был почтенный старец Усам. Автандил помог Усаму одолеть морских разбойников, грабящих их караван, Усам предложил ему в благодарность все свои товары, но Автандил попросил лишь простое платье и возможность укрыться от чужих взоров, «притворившись старшиною» купеческого каравана.
Так, под видом простого купца, прибыл Автандил в приморский дивный город Гуланшаро, в котором «цветы благоухают и не вянут никогда». Автандил разложил под деревьями свой товар, и подошел к нему садовник именитого купца Усена и поведал о том, что хозяин его нынче в отъезде, но «здесь Фатьма-хатун при доме, госпожа его супруга, / Весела она, любезна, любит гостя в час досуга». Прознав о том, что в их город прибыл именитый торговец, к тому же «словно месяц семидневный, он красивее платана», Фатьма тотчас велела препроводить торговца во дворец. «По летам немолодая, но красивая собою» Фатьма влюбилась в Автандила. «Пламя крепло, возрастало, / Обнаруживалась тайна, как хозяйка ни скрывала», и вот, во время одного из свиданий, когда Автандил с Фатьмою «целовались за беседою совместной», распахнулась дверь алькова и на пороге появился грозный воин, посуливший Фатьме за ее распутство великую кару. «Всех детей своих от страха загрызешь ты, как волчица!» — бросил он ей в лицо и удалился. В отчаянье залилась Фатьма слезами, горько казня себя, и умолила Автандила убить Чачнагира (так звали воина) и снять у него с пальца подаренный ею перстень. Исполнил Автандил просьбу Фатьмы, а та рассказала ему о своей встрече с Нестан- Дареджан.
Как-то на празднике у царицы Фатьма зашла в беседку, что была возведена на скале, и, отворив окно и посмотрев на море, увидела, как к берегу пристала ладья, из нее в сопровождении двух чернокожих вышла девушка, красота которой затмевала солнце. Фатьма повелела рабам выкупить у стражей деву, а «если торг не состоится», умертвить их. Так оно и случилось. Фатьма укрыла «солнцеокую Нестан в потайных покоях, но девушка продолжала денно и нощно лить слезы и ничего о себе не рассказывала. Наконец Фатьма решилась открыться мужу, который с великой радостью принял незнакомку, но Нестан оставалась по-прежнему молчалива и «уста свои, как розы, над жемчужинами сжала». В один из дней Усен отправился на пир к царю, которому был «друг-приятель» и, желая воздать ему за его благосклонность, посулил в невестки «деву, сходную с чинаром». Фатьма же тотчас усадила Нестан на быстроногого коня и отослала прочь. Поселилась в сердце Фатьмы печаль об участи прекрасноликой незнакомки. Как-то раз, проходя мимо харчевни, Фатьма услышала рассказ раба великого царя, повелителя Каджети (страны злых духов — каджей), о том, что после кончины его хозяина править страной стала сестра царя Дулардухт, что она «величава, как скала» и на попечении у нее осталось два царевича. Раб этот оказался в отряде воинов, которые промышляли разбоем. В одну из ночей, скитаясь по степи, они увидели всадника, лицо которого «в тумане, точно молния, сверкало». Признав в нем деву, воины тотчас пленили ее — «не прислушалась девица ни к мольбам, ни к уговорам <…> Только сумрачно молчала пред разбойничьим дозором, / И людей она, как аспид, обливала гневным взором».
В тот же день Фатьма послала в Каджети двух рабов с поручением отыскать Нестан-Дареджан. В три дня воротились рабы с известием, что Нестан уже помолвлена с царевичем Каджети, что Дулардухт собирается ехать за море на похороны своей сестры и что колдунов и чародеев она берет с собой, «ибо путь ее опасен, а враги готовы к бою». Но крепость каджей неприступна, она расположена на вершине отвесной скалы, и «десять тысяч лучших стражей охраняют укрепленье».
Так открылось Автандилу местопребывание Нестан. В ту ночь Фатьма «на ложе счастье полное вкусила, / Хоть, по правде, неохотны были ласки Автандила», томимого по Тинатин. Наутро Автандил поведал Фатьме историю о том, «как одетый в шкуру тигра терпит горя изобилье», и попросил послать к Нестан-Дареджан одного из своих колдунов. Вскоре колдун воротился с наказом от Нестан не ходить Тариэлу в поход на Каджети, ибо она «умрет двойною смертью, коль умрет он в день сраженья».
Призвав к себе рабов Фридона и щедро одарив их, Автандил велел им ехать к их повелителю и просить собрать войско и выступить на Каджети, сам же пересек море на попутной галере и поспешил с доброй вестью к Тариэлу. Не было предела счастью витязя и его верной Асмат.
Втроем друзья «в край Фридона степью двинулись глухою» и вскоре благополучно прибыли ко двору правителя Мульгазанзара. Посовещавшись, Тариэл, Автандил и Фридон решили немедля, до возвращения Дулардухт, выступить в поход на крепость, что «цепью скал непроходимых от врагов ограждена». С отрядом в триста человек день и ночь спешили витязи, «не давая спать дружине».