Situé dans la Basse-Casbah à Souk El Djemâa (marché du vendredi réservé à la vente des pigeons au temps des Turcs), le palais Dar Khedaouedj El Amia a été construit à l'emplacement d'une zaouia, celle de Sidi Ahmed Ben Abdallah El Djazairi (1469-1470). D'ailleurs, au rez-de-chaussée, subsiste toujours les vestiges d'un mihrab
Le palais fut acheté en 1789 par Hassan Kheznadji (ministre trésorier du dey Mohamed Ben Othman, auquel il succède en 1791) pour sa fille cadette Khedaouedj l'aveugle qui possédait aussi la villa Yusuf.
A son décès, ce sont Omar et N'fissa, les enfants de sa sœur Fatma (qui épousa le dey Hussein) qui en héritèrent. Les deux sœurs sont enterrées dans le petit cimetière où se trouve la "koubba" funéraire de Sidi Ben Ali qui, depuis, fut dénommée "Cimetière des princesses".
Habitée successivement par la famille Bacri, puis Gantois en 1830, la demeure fut récupérée par l'administration coloniale qui en fit la première mairie d'Alger. Une partie (celle ouest qui avait été agrandie) servit de « logement de fonctions » jusqu'en 1947. A cette date, le palais (enrichi de stucs, broderies murales hispano-mauresques vers 1860….) fut affecté au service de l'artisanat et, en 1961, il devint Musée des arts populaires.
En 1962, il devient Musée national des arts et traditions populaires.