Сейчас сложно сказать, когда вокруг памятников Миздакхана начала формироваться легендарная история. Очевидно, с глубокой древности Восточный холм имел значение святого места  на протяжении более тысячи лет:  на холме располагалось кладбище, и в доимсламское время и с приходом ислама.

Судя по  всему, архитектурные памятники на Восточном холме стали объектами посещения мусульманских паломников уже с XII века.

Вполне возможно, что немалую роль в этом процессе формирования легендарной истории Миздакхана сыграла община последователей суфийского шейха Сулаймана ал-Хаддади ал-Мусави (ум. в 1261). Не исключено, что ритуальные действия вокруг мавзолея Шамуна-наби и  возвышенности Джумарат-касаб когда-то поддерживались суфиями, проживающими на Миздакхане.

Одними из первых памятников Миздахкана, легендарная история которых стала достоянием науки, стали мавзолей Шамун-наби, «бугор» Джумарт-кассаб, и отчасти городище Гяур-кала. Выпускник кафедры этнографии МГУ Ю.В. Кнорозов посвятил этим памятникам свою дипломную работу. Частично она была опубликована в статье «Мазар Шамун-наби (Некоторые пережитки домусульманских верований у народов Хорезмского оазиса») // Советская этнография. 1949. Сс. 86-97.
Ю.В. Кнорозов отметил, что в ритуале посещения мавзолея Шамуна-наби и легендах вокруг этого памятника имеются пережитки домусульманских верований. 

В своей работе он привел рассказ шейха кладбища, согласно которому Шамун-наби был палван, живший задолго до Мухаммеда и боровшийся с кефирами за веру в истинного Аллаха. Он приехал из Аравии и поселился на этом холме. Рядом в крепости (городище Гяур-кала) жил неверный палван Гяур, с которым он часто боролся. Гяур увидел жену Шамун-наби, полюбил её и прорыл подземный ход к жилищу святого. По этому ходу неверная жена в отсутствие мужа ходила на свидание с Гяуром. Однажды Шамун-наби, возвратившись домой, не застал жену, пошел искать её, наткнулся на подземный ход и по нему попал в замок Гяура, где застал своего противника вместе с женой. Гяур стал бороться с Шамун-наби. Жена бросила под ноги мужу пригоршню проса, отчего тот поскользнулся и упал на колени. В этот момент собака Шамун-наби укусила Гяура и отвлекла его внимание. Борьба окончилась безрезультатно. После этого Шамун-наби завещал не хоронить его вместе с ногами, а отрубить их. 
Жена пыталась связать мужа веревками и даже проволокой, чтобы отдать во власть Гяура, но святой разрывал все узы. Случайно она узнала, что он не может освободиться, если его связать волосами из собственной бороды. Таким образом, Гяуру удалось победить Шамун-наби. Согласно завещанию, перед тем как хоронить его, святому отрубили ноги». 

Ю.В. Кнорозов указал, что существует доисламские корни легенды о Шамун-наби, которые восходят библейскому персонажу Самсону. Они проявляются в имени святого (Шамун-Самсон), гигантском росте, теме неверности жены; мотиве волос, играющих ключевую роль в силе героя. 

Холм Джумарт-кассаб, который, как показывают археологические раскопки, на протяжении длительного времени служил местом погребений (III-XIV вв.), впоследствии превратился в священное место, связанное с культом плодородия. Легенды утверждают, что под холмом находится подземный мавзолей, в котором похоронен благочестивый мясник Джумарт. 

«….Связь мазара Шамун-наби с бугром Джумарт-кассаб, отчетливо заметная в обрядовой практике, позволяет предположить, что в имени Джумарт традиция сохраняет имя древнего героя легенды, разрушенное святилище которого (по всей видимости, древнее на кладбище) заменил мазар Шамун-наби. Джумарт-кассаб, щедрый мясник, может быть сопоставлен с Гайомардом зороастрийских источников, упоминаемых в Авесте под именем Гайа Маретан, тогда как популярной пехлевийской формой было Гемурд.

В зороастрийской космогонии Гайомард - предок всех людей (из его семени произошла первая человеческая пара), сотворены Ахура-Маздой из земли вместе с первородным быком, предком животных. По Авесте, Гайа Маретан - первый праведник, последовавший установлениям Ахуры-Мазды, и предок народов арья (арийских народов)» (Кнорозов. 1949, С.91-92). 

Очевидно, что характер постройки - мавзолея Шамун-наби, перекрытого семью куполами – отразился в легендарном рассказе о семи дочерях героя, «и каждая выстроила ему по гумбезу». 

Гигантское надгробие в мавзолее (более 25 метров), которое является кенотафом, очевидно послужило основой для предания легендарному герою облика богатыря (палвана).

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

Считается, что таким образом можно излечиться от бесплодия. Согласно распространенному поверью, данный обряд помогает и при исцелении некоторых болезней. Для Джумарт-кассаб характерно действие, которое входит в обязательный ритуал паломников: совершающий обряд должен сложить пирамиду из фрагментов семи кирпичей («арвох уй»).  

По мнению историка М.Карлыбаева, в современном названии памятника соединяются два арабских слова: Халифа, в значение преемника основателя суфийского братства, старший ученик; Ережеп/Раджаб - арабское мужское имя.  

Руины здания, которые использовались в последние несколько столетий как кладбище, являются предметом зиарата среди местного мусульманского населения. Одно из ритуальных действий, совершаемых во время посещения паломниками Халифа Ереджеп, заключается в том, что они складывают из обломков сооружения пирамиды, состоящие из семи фрагментов кирпичей.  Очевидно, что этот ритуал никоим образом не связан с исламом. 
В тоже время, пытаясь как-то объяснить традицию сооружения пирамидок, среди людей, кто показывает туристам памятник, распространилась легенда, что руины Халифа Ереджепа являются своеобразными мировыми часами апокалипсиса. Дело в том, верхние части  трёх сохранившихся стен и другие конструктивные детали памятника   сложены из жженного кирпича. Неудовлетворительное состояние кладки наверху приводило к тому, что сверху время от времени падали жженные кирпичи.

Отсюда появилась легенда, что раз в год со стен здания падает один кирпич. И в тот  момент, когда упадет последний кирпич с верхушки стен Халифа Ереджепа  жизнь на Земле закончится.  Так Халифа Ереджеп получил символическое значение эсхатологических часов, а столбики, которые складывают паломники как бы возвращают эти кирпичи на место и продлевают жизни Земли.

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