Historiography has, in the last couple of decades, tackled in a critical and complex way the question of the inclusion of colonial artefacts and sites in processes of heritage recognition and protection. Such reflections, in the wake of collective research endeavours aiming at discussing the colonial history of heritage as a notion, a practice and an institutionalization process in general, have illustrated the difficult relationship between heritage conservation policies and conflicting memories in the case of situations involving a post-colonial dimension. In cities of North Africa and the Middle East, intense debates have emerged on heritagization choices and strategies. They often involve reflections on the category of heritage itself, on identity and on memory. The object of this paper is to examine such debates and situations to offer a deciphering of the complexity of what is at stake and a critical reading of ideological, political and social ambiguities. Discussing examples in formerly Ottoman cities colonized by France in the 19th and 20th centuries, the paper will analyse various phases and types of heritagization and/or rejection, in order to reflect on the entanglement of memories, but also on how colonial heritage considerations invite revised approaches to heritage in general.