Предполагается, что город возник примерно во второй половине XIII века. М. Г. Сафаргалиев полагал, что основание города произошло именно в это время, когда «правящая верхушка Золотой Орды приняла новую религию — ислам, и мусульманское духовенство стало получать от ханов различные привилегии».
Согласно общепризнанной точке зрения, первое упоминание Хаджи-Тархана в письменных источниках встречается в записках арабского путешественника Ибн Баттуты, который посетил этот город вместе с Узбек-ханом в 1333 году. Средневековые карты помещают Хаджи-Тархан на западном берегу Волги, несколько выше центра нынешней Астрахани. Сегодня остатки города фиксируются археологически на городище «Шареный бугор».
Далее: Путешествие шейха Ибн-Батуты в Золотую Орду, в половине XIV века