While Aladdin, Genie, and Abu are out of town for a diplomatic mission, Dominus Tusk attacks Agrabah. Jasmine is about to stop him, but her father tells her that it's too dangerous and he goes inside the palace to get something, with Iago following him. The Sultan and Iago go to a secret hiding place and find a statue of a muscular man named Kileem wearing an armor. The Sultan tells Iago that his father told him the legends that the man wearing the armor becomes invincible and the armor should never be worn because of tragic consequences. He removes the armor from the Kileem statue and green smoke comes out of it.
Meanwhile, Jasmine can't wait for her father to return, so she gets on Carpet and fights Tusk, but the minotaur hits her. The Sultan shows up wearing the armor and fights him. The armor makes him faster and stronger. After defeating Dominus Tusk, the Sultan starts acting a little strange. The next day, Aladdin, Genie, and Abu return to the city with a man named Akim, who is an ambassador of a place called Ganastan. When they enter the palace, they see that the throne room is filled with weapons and large horns and the Kileem statue is on the right side of the room.
Jasmine and Iago show up and tell them that the Sultan defeated Dominus Tusk. The Sultan, who is still in the armor, shows up and meets Akim. When the ambassador says "your stature," the Sultan gets uncontrollably angry. Everyone realizes that the armor not only made him faster and stronger, but it also changed his personality.
Later, Aladdin and Jasmine peek into the Sultan's toy room. Jasmine tells Aladdin that the only time he gets out of the room is when he trains the palace guards. When the Sultan gets out of the toy room, Aladdin takes a lock out of his vest so he and Jasmine can enter. Meanwhile, when the Sultan is training the guards with a rope, he calls Genie to use him as his opponent to teach the guards. Back in the Sultan's toy room, which is filled with various maps and scrolls, Aladdin and Jasmine read each scroll that talks about Kileem, who ruled Agrabah with an iron fist with his magic armor that made him "strong as stone." As he lay dying, Kileem left a dark promise that his legacy would return for the next person to don his armor. They then conclude that the armor cursed the Sultan and that Kileem is in his body. They then see a map that shows that Kileem will make the Sultan conquer all of the Seven Deserts.
The Sultan enters the room and Aladdin hides behind a tapestry and Jasmine hides under a table. But the Sultan finds Jasmine and the princess tells him that she approves his invasion plans. Aladdin later comes up with a plan to trick the Sultan into removing his armor. He and his friends, except for Iago and Jasmine, take the Sultan to the cliffs. Aladdin tells him that he has to cross the river in order to get to Ganastan. When the Sultan is angry about the gang taking him to a river, Genie blasts the Sultan with his magic, making him fall in the water. He tries to swim back up but the armor he's wearing is too heavy. Aladdin and the others wait for the Sultan to come out without the armor, but then they see that the air bubbles stopped appearing.
Aladdin makes Genie go in the water to see if the Sultan is alright, but the Sultan comes out of a sand and starts fighting them. Aladdin, Genie, and Abu get on Carpet to fly away, but the Sultan hits them with a palm tree knocking them down. Meanwhile, Jasmine is looking out the window waiting for the gang to come back. Then Razoul and the other guards take the princess to the dungeon. The Sultan enters and tells Jasmine that she will be executed.
Meanwhile, Aladdin, Genie, Abu, and Carpet are at an oasis. They hop on Carpet to fly back to Agrabah. Meanwhile, Jasmine is at a high tower about to get executed. When she gets to the platform, Razoul cuts the handcuffs and makes her escape. But the Sultan throws the princess off the tower, but Aladdin catches her. The Sultan sees that they're still alive and he jumps off the tower and lands on Carpet, who falls to the ground. Jasmine then tells Genie not to hold back, for the Sultan is not her father. With some reluctance, Genie transforms into Geniebot and starts blasting the Sultan with his laser cannon. At the same time, the gang hears, Iago, who is in a cage in the throne room, crying for help. When the gang goes to the parrot, he points them towards Kileem's statue. Though Aladdin thinks that it's harmless, he is proven wrong, as statue's eyes start glowing green. Realizing the truth to the meaning "strong as stone" meant that the statue itself empowers the armor and allows the spirit of Kileem to possess the Sultan, Aladdin runs towards it, but is repulsed by a blast of energy. Recovering, he declares that they have to destroy the statue. However, the Sultan appears, having beaten Genie after he mistakenly transformed into a toaster, proclaiming that the statue cannot be destroyed... at least not by the like of Aladdin.
Genie turns into a rocket and targets the statue, but instead he almost makes the palace explode. The Kileem statue is hanging over the edge with the Sultan hanging on to the statue, about to fall. The Sultan becomes his normal self when he asks them to help him, but when Aladdin does so, he turns into Kileem again and he throws Aladdin off the balcony. He then gets on the statue but his heavy weight makes the building collapse.
The Sultan runs to Aladdin, who dodges, making him crash into a slab of stone, breaking it, which gives him an idea. He gets in front of the Kileem statue and the Sultan runs towards him. As Aladdin jumps out of the way, the Sultan realizes too late what he had done and crashes into the statue, breaking it. Kileem's spirit gets out of the Sultan and disappears and the armor breaks apart. Everyone is happy that the Sultan is back to normal.