Kompleks pałacowy został założony przez kalifa Kordowy Abd ar-Rahmana III. Gdy Abd ar-Rahman III ogłosił się kalifem w 929 roku i ustanowił niepodległy kalifat Umajjadów, postanowił wybudować pałac w pobliżu Kordowy, który byłby dowodem potęgi władcy, zarówno dla poddanych, jak i dla władców innych państw. W czasie powstania kompleksu kalif kontrolował bowiem większość Półwyspu Iberyjskiego, a także rywalizował z dynastią Fatymidów o panowanie nad Afryką Północną. Nazwa obiektu pochodzi od imienia faworyty kalifa – Az-Zahry i oznacza dosłownie „miasto az-Zahry”. Budowa rozpoczęła się między 936 a 940 rokiem. Już w 941 roku został poświęcony meczet. Władca w latach 947–948 przeniósł z Kordowy do kompleksu cały swój dwór. Prace budowlane trwały do śmierci kalifa w 961 roku, pochłaniając corocznie jedną trzecią budżetu państwa.

Za czasów Al-Hakama II pałac przeżywał erę rozkwitu, odgrywał rolę stolicy islamskiego państwa al-Andalus i był siedzibą kalifa. Jednak gdy w 976 roku zmarł Al-Hakam II i rządy przeszły w ręce jego jedenastoletniego syna, Hiszama II, rozpoczął się upadek Mediny Azahary. Faktycznie władzę przejął hadżib Al-Mansur, który uwięził kalifa w pałacu. Kontrolował go do tego stopnia, że kazał zamurować przejścia łączące poszczególne części kompleksu pałacowego. Al-Mansur zmarł w 1002 roku. Jego następcą został jego syn Abd al-Malik, który rządził Al-Andalus jako hadżib aż do śmierci w 1008.

Po Abd al-Maliku przejął władzę jego brat Sanchuelo, z zamiarem zagarnięcia całego kalifatu dla siebie i całkowitego odsunięcia od władzy Hiszama. Wywołało to wojnę domową i rozbiło państwo na szereg mniejszych księstw, które nie były w stanie bronić się przed chrześcijanami. Około 1010 roku sama Medina Azahara została splądrowana. Dzieła zniszczenia dopełniły oddziały berberyjskich najemników, podpalając i burząc pałac. Najazd wymazał kompleks pałacowy i otaczające go miasto z mapy świata na prawie całe tysiąclecie.