Mosque architecture in Indonesia can be generally divided into two different styles. The first is based on the traditional wooden structure of Southeast Asia, in which a timber building with a hipped pyramidal roof is built on top of stilts. The second is more readily readable as “Islamic,” due to the use of arches, bulbous domes, and minarets on the building. In Southeast Asia, mosques of the second type were built only after the late- 19th century, and have been categorized as “Mughal/Mogul,” “North Indian,” “Indo-Islamic,” or “Indo-Saracenic” style mosques. In this article, I examine the architectural changes found in Indonesian mosques focusing on two examples of each style: the Agung Masjid Demak (Demak Great Mosque), which was built in the traditional style, and the Masjid Raya (or Baiturahman Mosque) at Aceh, which was built by the Dutch in the new, ``Islamic``, style. I argue that the new style of mosques reflected the conscious rejection of the traditional mosque and power structure on which it was based. I also suggest that these mosques be categorized as ``Colonial-Islamic style``, as they represented a European interpretation of Islamic architecture. Due to its eclectic features, as well as the rise of Islamic scripturalism during the early 20th century, the new colonial-Islamic style architecture came to be accepted among Indonesians as a symbol of the Pan-Islamic community, leading to many other examples built in this style after Independence.