La fortificació original es va construir sobre un antic establiment romà i més tard visigòtic. Va començar a prendre el seu aspecte de fortificació palatina, després de la conquesta de Sevilla, el 712 pels àrabs; que ja des de l'any 720 utilitzarien el recinte com residència dels seus dirigents. L'any 884 la fortalesa va contribuir a evitar una invasió dels vikings de la ciutat.

Des de la seva construcció inicial àrab, el conjunt incloïa diversos recintes, com la Casa dels Prínceps, habitatges que al segle ix anaven des de la Plaça del Triunfo fins al Barri de Santa Cruz. El primitiu palau islàmic és de la mateixa època que l'Alhambra de Granada, es va ampliar amb l'habitatge dels emirs al segle xi, també al segle xii es va continuar fortificant i afegint-li estances com l'Alcasser o Palau de les Benediccions, un segle més tard els almohades van sumar més patis i palaus. Actualment només es conserva el Pati del Yeso, resta de l'antic Palau Islàmic.

Després de la presa de la ciutat per Ferran III de Castella el 1248, es va convertir en allotjament reial, el seu fill Alfons X el Savi va portar a terme les primeres reformes després de la conquesta, ordenant el 1254 la construcció de tres grans salons en estil gòtic. Posteriorment el 1364, Pere I de Castella va decidir de construir el denominat Palau Mudèjar, que es va convertir en el primer palau d'un rei castellà que no estava protegit per murs i defenses d'un castell, i assolint l'aspecte mudèjar que avui conserva i que encara sorprèn per la seva riquesa i ornamentació. El 1366 quan va estar acabat el nou palau, va començar una guerra civil que va enfrontar a Pere I amb el seu germanastre Enric II de Castella, i que acabaria amb la mort del senyor Pere el 1369, i per això no sembla que el rei Pere, pogués gaudir del nou palau per molt de temps.[1] El palau de Pere I és considerat el més complet exemple de l'arquitectura mudèjar a Espanya. Posteriorment es van aixecar també la Capella Gòtica, el baixador, el Pati de la Montería i els Grotescs dels jardins.