Link's map told him to travel to the Desert of Mystery in southwest Hyrule. This was a long journey, and when Link finally arrived at the hot, sandy desert he decided to rest inside of a cave. This cave turned out to be the hideout of another troubled sage, Aginah. Link related his quest to Aginah, who helped him with a valuable piece of information. The sage had sensed that something was happening to the Golden Land the seven sages sealed, and believed this to be an omen of the Great Cataclysm foretold by the Hylia. This prophecy predicted that "the Hero will stand in the desert holding the Book of Mudora." Aginah told Link that the Book of Mudora could help him read the language of the Hylia people, and entreated him to get it from Kakariko Village.

Thanking the old man, Link left the desert and headed back to Kakariko Village. In the southern section of this village was the town's library, which was the home of hundreds of books. Link searched and searched through these books, but could not find one called the Book of Mudora. He was about to give up when he noticed a large green book resting on top of a book shelf towards the back. He tried to get it off from there, but he wasn't tall enough. Frustrated, Link used his Pegasus Boots to charge at the bookcase. This knocked the book down, and the ancient Hylian Book of Mudora was now his.

Link headed back through the Desert of Mystery, looking for the hiding place of the next Pendant of Virtue. On the way vultures circled him, waiting for him to drop dead from the heat. Huge sand monsters, called Geldmen, rose up from beneath the sand and tried to pull Link under with them. Link fought them boldly, and tried not to succumb to his terrible thirst.

At last Link arrived at an oasis, and drank greedily from a nearby spring. Close at hand was an ancient platform, and a stone monolith inscribed with the language of the ancient Hylian people. Using the Book of Mudora, Link translated the inscription to his own language, and read,

To open the way to go forward,
Make your wish here
And it will be granted.

Link had noticed that a staircase was blocked by a stone statue that looked like a frog's head. Link wished for the staircase to be opened, and immediately his wish was granted. The statue moved, and so did two other ones. The entrance to the Desert Palace was now open, and the exit was blocked. Link charged boldly up the stairs and into the mouth of the Palace.

The inside of the Palace was not much different from the outside; it was hot and sandy, and an army of Leevers rose up from the sand to hinder his progress. Inside the Palace Link found another ancient artifact: the Power Glove, a gauntlet which would help him lift heavy objects such as stones and boulders. He found an exit to the palace, where he saw another entrance blocked by heavy stones. Reaching a dead end, Link lit four nearby torches with his lamp, which triggered the wall to move. Through the now-exposed door Link found the lair of the dungeon's evil masters: the Lanmolas. These giant worms dove above and below the sand like graceful fish, throwing hard, rocky dirt at him. Link went for their heads, until finally all three monsters were defeated. The blue Pendant of Power was now Link's.