Si les salles Daraxa et le complexe du Patio de los Leones étaient destinés à devenir la nouvelle résidence personnelle de Charles Quint, un nouveau palais serait nécessaire pour répondre aux besoins fonctionnels et représentatifs de la cour.

L'idée de construire le palais de Charles Quint est née en 1526, à l'occasion du mariage de l'empereur à Séville et de son installation à Grenade au cours de l'été de la même année. L'architecte en charge du projet fut Pedro Machuca et la construction commença en 1533, après quelques années de désaccord sur sa conception et son emplacement. Le financement des travaux provenait des impôts imposés aux Maures en échange du maintien de certaines traditions. Des ressources provenant de la Casa de Contratación de Séville et de l'industrie sucrière de Grenade ont également été utilisées.

Après 1572, en raison de la rébellion maure dans les Alpujarras, la progression des travaux s'est ralentie et s'est finalement arrêtée en 1637, alors que l'édifice n'était pas encore complètement recouvert.

En 1923, l'architecte et restaurateur Leopoldo Torres Balbás a entamé un programme de restauration du palais, qui s'est achevé en 1958 avec la couverture de l'édifice.

Le palais a un plan carré avec une cour intérieure circulaire et a été conçu par Pedro Machuca. Son inauguration en 1533 est remarquablement précoce pour ses caractéristiques, qui sont de style maniériste : colonnes doriques au premier étage, ioniques au second, et une frise décorée de têtes de taureaux (bucranea) dans la tradition gréco-romaine. Par certains aspects, il reprend ou avance des solutions architecturales typiques du maniérisme italien, ce qui peut s'expliquer par le séjour de Machuca dans ce pays et sa capacité à développer de manière créative certains éléments du style maniériste naissant.

La façade du palais est entièrement de style Renaissance. Le premier niveau est de style toscan avec des coussins, tandis que le deuxième niveau présente des éléments décoratifs typiques du style baroque. Au-dessus de la porte principale se trouvent deux statues ailées de femmes allongées sur le fronton. Au sommet, trois médaillons encadrés de marbre vert contrastent avec la pierre. Sur les côtés sont représentées des scènes de la mythologie grecque, notamment deux des douze travaux d'Hercule. Les anneaux de fer en bas sont purement ornementaux, suivant la mode de Florence et de Sienne à l'époque.