The story opens with a band of robbers arriving in their hideout with their latest spoils. Just as their incompetent leader, Abis Mal, rouses the ire of his men, Aladdin and Abu steal the treasures back and distribute most of it among the poor of Agrabah - with the exception of a jewel flower, which Aladdin intends to give to Jasmine. Upon their arrival, Jasmine announces to Aladdin a surprise which the Sultan intends to reveal at this evening's dinner.
Meanwhile, in the desert, Iago manages to dig himself and Jafar's genie lamp out of the sand into which the Genie had fired them. Jafar orders Iago to release him at once, but Iago, tired of being treated badly by Jafar, throws the lamp into a nearby well. He returns to Agrabah, hoping to convince Aladdin that he had served Jafar only because he had hypnotized him just like the Sultan (even though it's not the truth). He meets Aladdin and insists that he is innocent, but Aladdin is not fooled and tries to capture him. While chasing Iago, Aladdin has a run-in with Abis Mal and some of his men, but is saved by Iago. Now willing to give Iago a fair chance, Aladdin returns with him to the palace, where they are greeted by Genie, who has returned from seeing the world and is glad to be home in Agrabah. That night, the Sultan announces that he wants to make Aladdin his new grand vizier. Trying to draw on the good mood, Aladdin attempts to persuade the Sultan to forgive Iago, but Iago inadvertently ruins the dinner and the Sultan and Jasmine are furious. With Iago's help, though, Jasmine eventually reconciles with Aladdin.
Meanwhile, Jafar, by luck, is found by Abis Mal. As Jafar is a genie, he is handicapped by the incompetence of his new "master". Jafar desires to be free so that he can get revenge on Aladdin and rule Agrabah, but needs Mal's co-operation to do this. Though Abis Mal is technically his master, Jafar still asserts his power by tricking Abis Mal into wasting two of his wishes and placing him in dangerous situations before making him return to Agrabah; however, Abis Mal willingly goes along with Jafar in order to get his own revenge on Aladdin. Once in the palace, Jafar reveals himself to Iago and forces him to play along with his plans. The next day, Aladdin and the Sultan depart to have a discussion at a place suggested by Iago. After they leave, Jafar confronts the Genie and Abu in the Palace gardens and shows his power, imprisoning the pair.
Meanwhile, Aladdin has a talk with the Sultan that earns his acceptance as the future grand vizier. When Aladdin thanks Iago, he is ambushed by Abis Mal, accompanied by a group of cloaked horsemen. Aladdin, helpless without Carpet (who is trampled by one of the horses), fails to prevent the Sultan's capture. When Carpet recovers, Aladdin gives chase, only to be shocked when the horses gallop off the cliff and sprout wings. Despite his surprise, Aladdin takes back the Sultan. He is about to make his escape when one of Abis Mal's horsemen creates a waterspout, sucking the Sultan off the carpet and into the waterspout. Aladdin turns the carpet back to save the Sultan, but he and the carpet are sucked in. Aladdin, however, is thrown back out and into the raging river. While struggling to stay above the surface of the water, Aladdin manages to grab a rock. But before he can catch his breath, Abis Mal kicks him back into the river, and he plummets over the edge of the waterfall. Abis Mal enjoys his moment of glory, but one of the horsemen uses magic to keep Aladdin from meeting his death. Aladdin then gently floats over the deadly rocks and is dropped into safer water.
It is finally revealed that all the horsemen were Jafar in disguise. Abis Mal rushes towards Jafar, expressing anger that Aladdin was saved, ("He was this close to being a greasy little smear on the rocks!") Barely keeping his temper, Jafar reminds Abis Mal of the plan and congratulates Iago for his work. Iago, however, is clearly distressed at betraying Aladdin. Come nightfall, Aladdin recovers on a river back. He is then left to crawl back to Agrabah on foot.
When he returns, Jasmine accuses him of murdering the Sultan and sentences him to death. Aladdin is shocked, but the truth is that Jasmine was also captured while Aladdin was away, and Jafar disguised himself as her when he issued the death sentence.
In the dungeon, Jasmine and the others berate Iago for betraying them, but their anger is quickly forgotten when Iago chooses to attempt to free Genie so he can save Aladdin. Jafar reveals himself to Aladdin moments before his execution, and Aladdin frantically attempts to tell the guards, but they don't listen. Finally, after a great amount of effort, Iago frees Genie, who saves Aladdin just as the sword falls, and then the others. Aladdin angrily goes off on Iago for setting him up, but changes his mind when Jasmine informs him that Iago freed them on his own. While Iago suggests that they run, Aladdin decides to attempt to stop Jafar. Genie tells Aladdin that, in order to destroy Jafar, his lamp must be destroyed before Abis Mal wishes him free. Iago chooses not to face Jafar, and the others let him go without blame on account of their new freedom.
Jafar and Abis Mal celebrate Aladdin's death, and Abis Mal wants his third wish. However, Jafar refuses unless the wish is used to set him free. He bribes Abis Mal by conjuring mass amounts of gold and treasure in exchange for using the third wish for setting him free, while Genie attempts and fails to steal Jafar's lamp without being seen by the two. But Abis Mal hesitates, suspicious of Jafar's motives. They soon spot Abu attempting to steal the lamp, Jafar, surprised and enraged to see that Aladdin is still alive, blows them out of the throne room into the palace garden. Aladdin and Abu are saved by Genie, and Abis Mal is caught on a tree branch, unable to reach the lamp or properly move, and the lamp falls to the ground.
Aladdin, Jasmine, the Genie, Abu and Carpet engage Jafar (in his monstrous genie form) in combat, but even when bound by the rules of the Genie he easily outmatches them, using his tremendrous powers to stop them from getting the lamp. His indiscriminate use of power opens a fissure in the ground which is filled with magma. Thoroughly trapped, Aladdin faces certain death when suddenly Iago reappears and grabs the lamp. Jafar blasts him, leaving him for dead, but Iago manages to recover for a moment and uses his last ounce of strength to kick the lamp into the magma; making Jafar violently implode into a cloud of dust, destroying him forever.
To the joy of all, Iago recovers from his injuries, since it is among a Genie's set of laws that he can't use his powers to kill. Amidst the celebration, however, Aladdin announces to the Sultan that he is not yet ready to become a grand vizier, because first he wants to see the world, and can't just stay in the Palace for now. Jasmine declares that she would join him, but Iago objects to this and continues to rant as the film ends.
After the credits, Abis Mal, still stuck on a tree branch, suddenly realizes that, with Jafar and the lamp gone, he will never have his third wish.