Hay constancia de que fue mandada fundar con el nombre de "Madina Mursiya" el 25 de junio del año 825 por el emir de Al-Ándalus Abderramán II con el objetivo de sofocar las revueltas entre yemeníes, muladíes y las castas dominantes hispanogodas que ensangrentaban las tierras de la Cora de Tudmir, así como para hacer más fuerte el poder del Emirato de Córdoba en una cora escasamente islamizada.