It was built during the 12-year reign of Paul Muad'Dib and the Fremen Jihad/DE. Imperial policy encouraged demands placed on the Guild Navigators/DE, which, along with the jihad, inflated the spice's high value, and soon Arrakis/DE became the wealthiest planet of the Imperium/DE. Spice trade financed its construction, while the conquered planets brought huge workforces which supplied most of the labor for the building of the palace, as well as whole structures, brought in heighliners to become part of the palace.
On an escarpment nearby, during the same period, Alia's Temple was astablished, a fitting companion to the Keep.
Apocryphal records say that Paul would be able to build the palace in 7 days, and it was only characeristic of his humility that it took longer:
According to a legend among the Qizarate/DE (cf. Yiam-el-Din), the palace was built in the course of only 7 weeks, according to the plan of "ancient scriptures", believed to refer to the building of Jerusalem in OCB, Prophets LXXXIX, 24-26).
A curious myth also say that Paul modeled the building not only on the story of Jerusalem but also on that of Solomon's Temple, which took 7 years to complete. The main purport of the Temple-building myth is simply that Solomon employed multitudes of djinn in its construction. The Azhar Book/DE traces one myth concerning a shameer that was a magic pebble, and according to an obscure Fremen tradition Solomon employed a worm called Shamir to cut the stones for his Temple. The myth says that Paul, likewise, allied or commanded Shai-hulud/DE, the emperor of sandworms/DE, and he employed them to bore through the foundations. The work of cutterays and plasmeld structures are supposed to be actually the production of sandworm teeth and sandworm furnaces.
It was so big that it reeked of terrifying physical power; a dozen ancient cities could fit inside its walls. Paul and Chani/DE could live a nomadic life inside. The stone walls lowered the temperature, despite the best Ixian space heaters. Trees from many worlds were brought.
There were reception halls and formal meeting plances, ceremony halls, an inner section for communications, and a Great Hall for public audiences. A whole wing is for his personal guard. In a room far beneath Paul kept a stunted sandworm/DE surrounded by water moat to poison it, in order to foresee the future. The holding cells, carved with cutterays from the veined brown rock beneath the Keep.
The palace was traversed by endless vaulted passages were lit by triangular metaglass windows and paved with tiles figuring water creatures from exotic planets, oval doors with winking lights with Ixian handiwork: pneumatic transport orifices. Nearer the Grand Reception Hall, arching was different, pillared supports were gradually amplified, while triangular windows were displaced by larger, oblong shapes; architectural tricks resulting to larger passages.
The Hall itself was entered through a 80x40 doorway from a tall antechamber. The doors swung inward silently, operated by Ixian machinery. The interior of the Hall itself was larger than any citadel of any ruler in human history. Its open sweep and its faraway domed ceiling, trusses and supporting beams were behind the walls, demonstrated the engineering genius behind it, hidden structural forces balanced with nicety. Its focus, the Imperial throne, had been cut from a single green emerald, the most precious possession of Hagar, a subject planet.
Behind the throne was a passage leading to a 20m3 cubic private chamber, lit by yellow glowglobes, with the walls adorned by deep orange hangings of a desert stilltent. It was vented with a grillwork through which it looked over a deep abyss. An arc footbridge constructed of crystal-stabilized gold and platinum,decorated by fire jewels from far Cedon, led to the galleries of the inner city across a pool and fountain filled with waterflowers with blood-red petals.
Within view, in other directions, were the lower buildings of the government warren, colossal extragavant structures, from terraces like mesas, squares as large as cities, parks, premises, bits of cultured wilderness, a postern from ancient Baghdad, a dome dreamed in mythical Damascus, an arch from the low gravity of Atar, orchards and groves, open plantings to rival those of fabled Lebanon; all mixing magnificence and artistry with barbarity and dismal tastelessness.