King Kundamir has a son, ‘Ajib, who is a great fighter but also a tyrant. At one point he is thrown into prison, but the viziers have him released. He later assassinates his father and takes over the throne. He has a dream which is interpreted to mean that one of his brothers will cause him trouble. He inspects his father's harem and learns that one of the concubines is pregnant. He orders her drowned, but the executioners take pity on her and leave her in the woods, where she gives birth to a son, Ajib's half-brother, whom she names Gharib.
They meet Emir Mirdas of the Banu Qahtan, who marries the former concubine and has a son named Sahim al-Layl with her. Gharib grows up to be a good fighter and rider. Another tribe, angry because Mirdas would not marry his daughter Mahdiyya to their leader, attacks them and kidnaps the girl. Gharib, who has fallen in love with Mahdiyya, rescues her, but Mirdas is enraged by their love and plots his death. Fortunately, Sahim al-Layl warns Gharib, but Mirdas still refuses to approve a marriage and tells him to prove himself by performing an impossible task. He must conquer the Castle of Ham ibn Shith ibn Shaddad ibn Khalid in the Valley of the Blossoms, which is ruled by a black giant who killed another son of Mirdas.
Gharib climbs the mountain and finds a three-hundred-year-old man, who tells him about the one God. Gharib becomes a Muslim, as do his troops and his half-brother Sahim al-Layl. The castle's master, Sa'dan the ghoul, is a cannibal. Gharib defeats four of Sa'dan's five sons and then defeats Sa'dan, who converts to Islam and joins his army. In the castle, Gharib finds treasures and prisoners. One of the prisoners is Fakhr Taj, the princess of Persia. Her father, King Sabur, is a fire worshipper, and she was kidnapped on her way to their temple. Gharib sets out to return her home, vanquishing the Banu Qahtan's troops on the way and convincing them to convert to Islam.
Sabur agrees to a marriage between Gharib and Fakhr Taj as long as Gharib first slays his enemy Jamrqan. After a tournament, Gharib gets drunk and makes love to Fakhr Taj. Elsewhere, Emir Mirdas promises Mahdiyya's hand to ‘Ajib, who hears that Gharib is alive and is conquering al-Jazira and Iraq. The two brothers go to war, but on separate occasions each is drugged and kidnapped but manages to escape. Finally Gharib's army is victorious and he takes over Kufa, but ‘Ajib and Mirdas flee with Mahdiyya.
Mirdas is conquered by Jamrqan, only for Jamrqan to fall before Gharib. ‘Ajib hides in the city of Oman. Gharib leaves Mahdiyya in the care of another king and continues to Oman, which his forces conquer, but their leader refuses to convert and is executed. Once again, ‘Ajib escapes.
Gharib and Sahim al-Layl take a relaxing trip to a valley, but fall asleep and are captured by two jinn, because they unknowingly shot at a bird that was really a jinni. They are taken before King Mur'ash, the four-headed jinn king, but every time he tries to execute them, some accident of fate saves them. Finally, he converts to Islam along with all his people and helps Gharib fight. Wielding the sword of Japhet and riding a winged horse, Gharib helps vanquish jinn rulers Barqan and the Blue King. In the Blue King's palace, he finds the abducted princess Kawkab al-Sabah of China and falls instantly in love with her. He and his brother go back to the human world. ‘Ajib, meanwhile, escapes to India, but Gharib conquers that place too and this time captures him. ‘Ajib and the king of India are killed after refusing to convert. Gharib is finally able to marry Mahdiyya.
He conquers the land of King Sabur. King Sabur was angry that Gharib made love to Fakhr Taj before marriage, and she was abandoned by a river. Gharib goes after her but is attacked by her brother and his armies and is left floating on a raft in the river. Some unbelievers find him and he converts them and escapes. He is periodically captured by jinn but finally makes it to the palace of Jan Shah, an idolatrous queen. He breaks her idols and in retaliation she turns him into a monkey. After two years, she releases him, on the condition that he make love to her. He plays along, but kills her.
He returns to his wives, Kawkab al-Sabah and Mahdiyya. Murad Shah, Gharib's son by Fakhr Taj, seeks revenge on his grandfather and attacks Sabur's capital. However, it is now under Gharib's rule, and the father and son battle before they've recognized each other. Finally, all the infidels are defeated, Murad Shah becomes king of Persia, and everyone lives happily.