According to the legend Sheik had told him, Link's last destination was a "goddess of the sand." Link had been to Gerudo Valley briefly before, but hadn't explored it very much. When he arrived, the wooden bridge across Zora River's had been cut. This didn't stop Link; using the Longshot, he soon was on the other side of the gorge. He noticed a tent that had been set up, and headed for it to take a rest.

The tent belonged to an old man, who said that he was a master craftsman. Link was curious to know how the craftsman had gotten stuck on this side of the broken bridge. The craftsman said that the Gerudo thieves had broken the bridge. He wanted to fix the bridge, but his workers were all gone. They had said that working as carpenters wasn't cool, and run off to Gerudo's Fortress to become thieves.

Link told the old man about his quest, and the stranded craftsman asked him to find out what had happened to his workers, since Link was going to the fortress. Link continued on toward Gerudo's Fortress, but when he arrived he was greeted by a rude surprise: the female guards took him prisoner and threw him into a room high up in the fortress, telling him to keep quiet. Link hadn't expected a friendly reception, but imprisonment? Link waited until they left, and then hookshot his way onto a ledge.

Escaping back onto the ground, Link sneaked through the fortress, looking for the missing carpenters. He found one of them locked up in a cell, and looked for a way to free him. Suddenly, the prisoner yelled for Link to watch out, and Link spun around to face a female Gerudo guard. The guard was quite skilled with her twin blades, using them both to attack and defend, but at last she admitted defeat, dropped a key, and disappeared.

Link freed the carpenter, who introduced himself as Ichiro. The guards had locked them up just because they were male, and they were no longer interested in joining the rough female Gerudos. He promised to reward Link if he freed his fellow carpenters, and escaped to safety. Link continued to search through the fortress, sneaking past guards and shooting some of them with arrows to stun them.

Eventually he saved two others, Jiro and Sabooro. The fourth prisoner, Shiro, told Link a piece of information he had overheard the Gerudos talking about:

"In order to cross the Haunted Wasteland, you'll need the 'eye of truth.' The Colossus is on the far side of the wasteland."

Link was just about to leave, when he was stopped by the voice of a Gerudo. She was in charge of the thieves' hideout, and told Link:

I've seen your fine work. To get past the guards here, you must have good thieving skills. I used to think that all men, besides the great Ganondorf, were useless, but now that I've seen you, I don't think so anymore! The exalted Nabooru, our leader, put me in charge of this fortress. Nabooru is second-in-command to the great Ganondorf, King of the Gerudo Thieves. Her headquarters are in the Spirit Temple, which is at the end of the desert.

Believing that Link was aspiring to join them, the Gerudo granted Link a Gerudo Membership Card, which gave Link free access to all areas of the fortress.

Before he continued his journey, Link went back to visit the carpenters in their tent in Gerudo Valley. On his arrival he saw that the carpenters had repaired the bridge across the gorge. Talking to some of them, he learned more about Nabooru:

The leader of the gang of thieves is Nabooru. She is experimenting with brainwashing many people at the ruins in the desert.

When Nabooru was a lone wolf thief, she never stole from the weak, but... Now, Nabooru's gang of thieves stands for cruelty and brutality. She claims to be a chivalrous robber, but...no way!

This Nabooru was shaping up to be an interesting character, so Link headed back to the Gerudo fortress to arrange a meeting.