Situé à l'angle nord-est de la forteresse, il subit de nombreuses transformations au cours des siècles. Édifié dans la seconde moitié du XVIe siècle, il conserva pendant les XVIIe et XVIIIesiècles une fonction essentiellement militaire, bien qu’il abritât les assemblées du Dîwân. Une garnison de janissaires en assurait la défense. Au début du XIXe siècle, le dey ‘Alî Khôja, craignant les émeutes populaires, y fit édifier son palais, début d’une série de transformations.


Deux entrées principales y donnent accès. L’une conduit par une porte voûtée à la cour, l’autre du coté de la rue mène à une entrée en chicane qui permet de préserver l’intimité de la maison ; cette formule, déjà présente dans l’Antiquité, se rencontre aussi bien dans l’architecture civile que militaire. L’entrée en chicane donnait accès à une salle centrale ornée d’une fontaine en marbre et d'une coupole semi-circulaire aux murs ornés de céramique et de peintures


Quatre ailes construites sur trois étage, entourent une grande cour rectangulaire, noyau central du palais, qui comprend les appartements du Dey avec un petit pavillon en bois très décoré dit « pavillon du coup d’éventail », des cuisines, un hammam, une salle de musique dont le mur du fond est décoré par une arcature avec des petites colonnettes. Le harem se trouve dans l’aile nord-ouest du palais ; zone indépendante réservée aux femmes, il s’organise autour d'un patio construit au dessus du Dîwân et du trésor.


Les carreaux de céramique qui garnissent les murs du palais présentent en général des compositions florales et végétales. Inspirés de l’art italien, ils sont importés d'Europe et de Tunisie. La plupart des carreaux que l'on trouve ici sont tunisiens : rien d'étonnant à cela puisque les relations commerciales maritimes avec Tunis étaient aisées et à peu près constantes. Les autres proviennent d'Italie, de Hollande et d'Espagne.

L’inspiration des décors de la céramique tunisienne est à rechercher dans les répertoires décoratifs andalou, turc, persan sinon européen. En effet, la technique doit beaucoup aux artisans andalous installés dans le quartier des Qallaline. Les influences persanes, anatoliennes, syriennes se sont mélangées aux éléments andalous après l’exode en Tunisie de 80 000 musulmans chassés d’Espagne par Philippe II en 1610. De l’époque ottomane, nous n’avons pas de données fiables si ce n’est le site de Tlemcen qui pourrait avoir produit les petits carreaux de pavage estampés à couverte brune, verte ou jaune et quelques plaques de céramique à entrelacs géométriques que l’on retrouve dans les demeures et mosquées algériennes.

Le palais témoigne également de l’histoire contemporaine de l’Algérie. En effet, c’est sous ses deux colonnades qu’en 1827 le célèbre « coup d’éventail » du dey Husayn fut infligé à l’émissaire français, événement prétexte à l’expédition militaire qui s’ensuivit. Durant l’occupation, le général De Bourmont modifia la structure du palais afin d’en faire son lieu de résidence. La forteresse fut coupée en deux par une route et isolée des autres édifices qui la jouxtaient.