Из Керчи путешественник отправился в порт Кафу (Феодосию), а оттуда в Солдайу (Судак) и г. Солхат (Старый Крым), затем по западному побережью Азовского моря он добрался до г. Азак (Азов) и оттуда перебрался в г. Маджар. Здесь, узнав о том, что султан Узбек-хан находится на летовке в местности Биштаг (Пятигорье), он направился туда, а затем вместе со ставкой султана в г. Хаджи-Тархан (Астрахань). В городе Астрахани, который служил осенней резиденцией султана Узбека, путешественник провел некоторое время и, узнав о том, что одна из жен султана — византийская принцесса Байалун отправляется на родину, в Константинополь, решил примкнуть к ее свите. 18 сентября 1332 г. Ибн Баттута в свите царицы Байалун прибыл в Константинополь, который произвел на него большое впечатление. Ибн Баттута провел в Константинополе 36 дней и 24 октября 1332 г. покинул его с большими почестями и щедрыми дарами императора. Не останавливаясь более, через Южную Россию он поехал в Астрахань и, не застав там Узбек-хана, отправился в столицу Золотой Орды — Сарай-Берке.
Из Сарая Ибн Баттута предпринял кратковременную поездку в Булгар. «Я захотел совершить поездку туда, — пишет он, — дабы самому убедиться в услышанном, увидеть короткую ночь в одно время года и короткий день — в другое». Там он составил маршрут путешествия на Печору (в «страну мрака»), но из-за большой опасности отказался от него и возвратился в Сарай. Путешественник пробыл в столице Золотой Орды — Сарай-Берке всего несколько недель и в середине января 1333 г. направился оттуда в Хорезм, северную провинцию Средней Азии. По его словам, он провел в пути «сорок дней» и наконец прибыл в Ургенч, столицу Хорезма, поразивший его богатством природы и оживленной торговлей.