- "There it is in all its glory -- the palace of Ali Bey. It's probably been a hundred years since anyone set food inside... possibly because there does not seem to be a door."
- ―Indiana Jones[src]
Ali Bey's Palace was a stone fortress located eastern Africa, in the Mombasa region of Kenya. It was built under the rule of Ali Bey, Emir of the Ottoman Empire in the sixteenth century. The Invincible Ruby was housed in a stone box carved by Wohat in an underground burial chamber.
The palace had a single entrance, which required the correct placement of the five mammalian Wohat Statues to unlock. The correct order was Giraffe, Lion, Monkey, Tiger, Rhinoceros. Clues to solving the puzzle of opening the door were inscribed on the door. As the centuries passed, the jungle grew up around the palace, hiding it from outsiders.
At some point, several persons found their way into the palace, but died inside, leaving their hat-wearing skeletons behind.
In 1931, René Belloq and Ali Bey-Faisal found the palace, and realized that they needed the five mammalian Wohat Statues in order to enter. Bey-Faisal and his henchmen began stealing the statues from museums around the world, and Indiana Jones caught up with them in Barcelona. Belloq and Bey-Faisal allowed Jones to steal the pieces from Belloq's hotel room, and let Jones reach the site and discover how to use the pieces to enter the palace.
With the five carvings, Jones flew to Nairobi, and drove to the jungle near Mombasa, and discovered the ruins of the palace. After barely translating the inscription, he used trial and error to arrange the five animal statues, but succeeded in opening the door. At this point, Bey-Faisal and his two henchmen captured Jones at gunpoint. Bey-Faisal explained that Belloq's team had been unable to gain entry to the palace, and needed Jones to open the entrance, and now that Jones had done so, he was no longer needed. Shocked that Belloq would order him killed, Jones realized that Bey-Faisal was planning to double-cross Belloq. Bey-Faisal admitted this plan, claiming the ruby as his birthright as a descendant of Ali Bey. Before he could shoot Jones, Bey-Faisal was pistol-whipped by Ballantine Gruber, who then escaped with Jones into the palace.
Recovering, Bey-Faisal and his men gave chase. When the the henchman with the goatee saw a shadow wearing a hat, he silently indicated the target to his boss, who fired at it, but it was only a skeleton. Meanwhile, Jones and Gruber had gone further into the dark ruins, where they fell through a weakened floor into an underground chamber and were knocked unconscious. Regaining consciousness, Jones pocketed the bullets from Gruber's pistol, and then found the stone box with Wohat carvings. Bey-Faisal's men located where Jones and Gruber were and reported to Bey-Faisal who dismissed them from his service, and snuck up on Jones' location.
Jones and Gruber pushed the lid off the box and discovered the ruby, but Gruber drew his gun to claim it for himself. Jones confronted the crooked Gruber about the theft of the Wohat crocodile from his own museum, and Gruber eventually confessed that he had arranged for its theft and sale on the black market. Attempting to silence Jones, Gruber pulled the trigger and was surprised when Jones showed him the stolen bullets. Gruber tried to seize the ruby, but was stopped by Bey-Faisal. Gruber punched Bey-Faisal aside, then held up the ruby, despite Jones' warning. The ruby activated its mystical power, and Gruber was reduced to a pile of ash. The building began to crumble and Bey-Faisal began to search for the ruby. Jones warned him of the impending collapse, but the obsessed Bey-Faisal paid no attention to Jones, and was crushed by a falling stone. Jones managed to escape as the castle fell into ruins. Heading through the jungle, Jones encountered Belloq and told him that if he wanted to find Bey-Faisal, he'd better be prepared to dig.