The palace was built in 1196 during the Southern Song Dynasty (1127-1279) for worshiping the sea goddess Ma-Tzu. According to historical records, Ma-Tzu, originally named Lin Moniang, was born in 960 during the early Song period. A smart child, Ma-Tzu could cross the sea on foot alone. With such an extraordinary ability, she saved a lot of fishermen from drowning. On September 9, 987 (a lunar year), Ma-Tzu ascended to heaven and became immortal on the Meiyu Peak of Meizhou Island. Locals erected a temple -- the ancestral temple of all other Ma-Tzu temples around the world -- on the peak that year in her honor. Legend has it that Ma-Tzu, or the Goddess of Straits, continued to protect ships at sea even after her death. Past emperors have conferred titles of nobility on Ma-Tzu, calling her the Princess of Heaven and Empress of Heaven. Chinese people at home and abroad have erected temples to Ma-Tzu called the Princess-of-Heaven or Empress-of-Heaven palaces along the coast.

The Quanzhou Empress-of-Heaven Palace was originally a gathering place for seafarers. In 1415 during the Ming Dynasty (1368-1644), Zheng He was ordered to rebuild the temple. From then on, all Ming envoys to Southeast Asian countries held sacrificial ceremonies in the temple. In 1680, having recaptured Taiwan, Emperor Kangxi of the Qing Dynasty (1644-1911) conferred the title Empress-of-Heaven Palace on the temple. Managing to retain their former grandeur, the present temple constructions include the main hall, back hall, wing pavilions and the east corridor. The front hall is three rooms wide and four rooms deep with a double-eaved gable and hip roof. Two Brahmanic-style stone columns stand in the back hall.