One day, Asmodeus, the King of the Genies, summons his lowly pupil Genii-Ali Mahmud to the Magic Kingdom. Ali, whose fondness for women and wine have rendered him an abysmal failure of a genie, is given one last chance to redeem himself. Asmodeus explains that because Raschid, the elderly king of Baghdad, has no heirs, the future of the city rests on the marriage of the young prince Husan, son of the honorable Norodeen; to the princess Yasmin, daughter of palace bookkeeper Shamadin. Swayed by the words of the Oracle, Raschid has declared that the offspring of Yasmin and Husan will constitute the new royal dynasty. Telling Ali that his mission is to insure the marriage, Asmodeus gives him a flying horse with which to reach Baghdad. In Baghdad, meanwhile, the young prince gives the young princess a grass ring, sealing their future union. Upon arriving in Baghdad, Ali is distracted by a comely woman, and while he dallies, Julinar, the Sultan of Cairo, invades the palace, slays Raschid and assumes the title of king. To save his own life, Shamadin suggests that Julinar marry Yasmin when she comes of age, thus assuring the legitimacy of his claim to the throne. To eliminate his rival for Yasmin’s affections, Julinar puts a price on Husan’s head. Fleeing for his life, the young prince hides in a basket belonging to nomadic tribesmen and escapes the palace gates. When Meroki, the tribal chieftain, discovers Husan, he takes the boy under his wing. For failing his mission, Ali is demoted to the status of a mere mortal and his horse is grounded. Seven years later, Ali has been promoted to court magician after the beheading of his superior. Yasmin, who has now grown to adulthood, still honors her betrothal to Husan and rebels when her father insists that she marry Julinar. When Norodeen objects to the match between Yasmin and Julinar, he is jailed. Although Ali’s horse can no longer fly, he has mastered the art of conversation and delights in giving Ali advice. The horse directs Ali to visit Norodeen in his cell and give him his magician’s cloak and turban as a disguise. Posing as the magician, Norodeen leaves the prison mounted on Ali’s horse. The horse then takes Norodeen to a caravan that can transport him to the town of Samarkind. When the caravan chieftain learns that there is a price on Norodeen’s head, however, he decides to turn him in for the reward. From the hills above, meanwhile, Meroki and Husan spot the caravan and its cargo of slave girls and decide to liberate the women. After Meroki and his tribe prevail, Norodeen is reunited with Husan, who is now known as “The Desert Hawk” for his prowess. When Norodeen informs Husan that Yasmin has agreed to marry Julinar, Husan decides to raid Baghdad and prevent the marriage. Later, inside the walls of the city, Husan incites the guards, thus attracting Yasmin’s attention. Failing to recognize the now grown Husan as her childhood sweetheart, Yasmin orders him brought to the palace to challenge Julinar’s gladiators. After Husan defeats Julinar’s fiercest warrior, Julinar appoints Husan captain of Yasmin’s bodyguards. Attracted to her virile bodyguard, Yasmin begins to flirt with Husan, and when he passionately kisses her, she senses that she has met him before. Husan, however, believes that Yasmin has betrayed him and does not reveal his identity. Witnessing their embrace, Ali, unaware that the bodyguard is really the young prince, conceives of a plan to eliminate him, Julinar and Shamadin. After telling the jealous Yasmin that the bodyguard is to meet a barmaid that night at a wine shop, Ali informs Julinar that Yasmin is planning to elope with a commoner and advises him to follow her. Ali then tricks Shamadin into leading a contingent of soldiers to the wine shop, hoping that they all kill each other in the melee. Norodeen also goes to the shop to alert Husan that Meroki’s troupes are ready to attack. Emboldened by the impending assault, Husan finally reveals his true identity to Yasmin when she follows him to the shop. When Shamadin and his men burst in and arrest Norodeen and Husan, Julinar praises Shamadin for uncovering Husan’s hideout, leading Husan to think that Yasmin betrayed him. Awakening from a drunken stupor, Ali learns of Husan's arrest and realizes his blunder and his horse announces that he is quitting in disgust. Screwing up his courage, Ali demands that the Oracle provide him with a flying carpet to take him to Asmodeus. There, a defiant Ali asserts that Yasmin and Husan will marry and ascend to the throne, then demands that Asmodeus restore his powers so that he can arrange the match. Pleased by Ali's’ newly found gumption, Asmodeus promotes Ali to genie first class. Outside the gates of Baghdad, Ali meets Meroki and plots to free Husan. On the day that Norodeen and Husan are to be beheaded, Ali transforms the executioner’s sword into a feather. After Husan grabs the feather, it turns back into a weapon, allowing him to defend himself. As Ali misdirects the guard’s arrows, Meroki and his men arrive and a battle ensues. After Husan disarms Julinar, Ali turns the would-be king into a parrot. With Husan and Yasmin reunited, the prophesy is fulfilled and Ali then turns the grass ring into a gold wedding band.