During a raging desert battle between the cities of Basra and Baghdad, soldier Basran is fatally wounded. Before dying, Basran takes a medallion from his killer's neck and gives it to his son Harun, urging him to somehow end the senseless killings.
Harun rides to Baghdad and meets shopkeeper Barcus. Harun strikes a deal in which, for ten dinars, he can pick any item in Barcus' shop. Under a pile of rags, he finds a magical golden sword that allows him to cut through solid metal. The sword will only manifest its powers when Harun wields it. Barcus warns him to be careful until they can translate the inscriptions on the blade.
Meanwhile, Vizier Jafar urges Badgad's Caliph to fight Basra. This is all part of a plot to undermine the Caliph's reputation. The Caliph refuses, more worried about his rebellious daughter, princess Khairuzan. Jafar suggests that her headstrong ways may be tamed by marriage to Hadi, the Vizier's son. After learning of the arranged marriage, Khairuzan disguises herself as a boy and escapes the palace, stealing Harun's horse in the process. She is finally caught by both Hadi and Harun, who begin to fight. Harun wins and discovers he is invincible while wielding the golden sword.
Khairuzan claims to be a boy slave and Harun brings her to the city, where they learn from Barcus that the sword's first inscription promises that whoever unsheathes the sword will gain the throne. Later, Harun realizes that Khairuzan is a girl. He protects her when a guard questions them, and they are both thrown to the dungeon, where they fall in love and kiss. After a minor quarrel, Khairuzan makes herself known to the guards and moves back to her harem. Knowing of the sword's magical powers, she declares that only the winner of a tournament may claim her hand. She names Harun as her guard, and despite being infuriated with his new predicament, he watches admiringly as she is very kind to the poor townspeople.
Meanwhile, Khairuzan's handmaiden, Bakhamra, informs Hadi about the magic sword. He and Jafar drug Harun, steal the sword and replace it with a replica. Khairuzan wakes Harun from his stupor and asks why he has not signed up for the tournament. Thinking that he is not aristocratic enough to marry her, Harun is surprised by this question, and the two share a kiss. He then races to Barcus and proclaims his newfound joy. Barcus warns him that the second inscription counsels that the bearer's true reward will arrive in a grave of stone. Nonetheless, Harun refuses to listen.
At the tournament, Hadi defeats Harun by cheating. Harun realizes his sword was switched and suspects Khairuzan to be responsible. After being jilted by Hadi, Bakhamra reveals his scheme to Harun. Hadi is about to bring his unwilling bride to bed, when Harun finds him. Captured by Hadi's guards, Harun is brought before Jafar. Bakhamra and the Caliph overhear the vizier's plan to kill them and blame Harun. When the Caliph orders Jafar arrested, the vizier brings out his medallion, which is identical to the one Harun carries. Trying to kill the Caliph, Jafar slices the magic sword into a stone pillar, where it remains stuck. The guards kill the Caliph and go after Harun and Khairuzan, who escape and fabricate their deaths.
Jafar and Hadi soon discover that they cannot pull the sword out of the column and call men in from across Bagdad to attempt to pull it out. While Khairuzan gathers the townspeople around her, Harun and Barcus sneak back into the palace. Harun fights with the guards and is almost captured when Khairuzan and her people storm the palace. He grabs the sword from the stone, causing it to collapse on top of Jafar and Hadi. After Khairuzan bestows on Harun the title Al-Rhashid (the righteous), the two kiss.
