The Odiferans are coming to Agrabah to wage a war. Aladdin and his friends see that the city is under attack but they don't know why. Aladdin then sees Nefir with the Sultan. The Sultan tells him that Nefir is his new war advisor and that he warned him about the attack. Aladdin tells him that he can't trust the imp but Jasmine wants him to hear her father out. Nefir takes a sheet off the model of Agrabah and shows everyone fans opening up, telling them that they will prevent the bombs from hitting them. He then makes his imps build fans in front of the palace.
A cheese bomb hurtles towards the palace and one of the imps pulls a lever to make the fans open up. Nefir then tells the Sultan that he can put him down for the "deluxe chief executive package" and the Sultan agrees, but Aladdin tells him that he can't trust Nefir. The Sultan tells the Aladdin that he should since Nefir's imps can protect Agrabah. Nefir then tells the Sultan that the barbarians from Odiferous are attacking the city and everyone finds that hard to believe because they're their friends and allies. After another cheese bomb flies into the throne room, Nefir's imps fly around the Sultan and make him a new outfit, for a price. The Sultan then makes two guards bring them a chest full of gold coins and Nefir and his imps fly away with it.
Meanwhile, the Odiferans have set up a camp. An Odiferan soldier tells General Gouda about Agrabah being protected. Uncouthma suggests that the war is over, but Gouda tells him that they can't return to their country until they smash the Agrabanians, calling them "flimsy fiends". Uncouthma tells him that they are their friends. Nefir and his imps enter their tent and talks to them about someone stealing their Most Sacred Crock of Cheese. Gouda then says that they will keep fighting until the Sacred Crock is surrendered. Nefir makes his imps build a catapult into a machine that fires huge diamond-tipped javelins. The leader of the imps then hands Uncouthma a bill, but the Odiferan prince won't take it and he hands a chest of coins to the imps. When Nefir and his imps leave the Odiferan camp, the Odiferans fire the javelins, making them go through the defensive fans and lodge in the palace.
Nefir returns to the palace and suggests that the Sultan uses an offensive weapon (or two). Aladdin suggests that they find out why the Odiferans are attacking the city, but Nefir says that Barbarians only understand action. Aladdin then says that it's a catastrophe and the Sultan tells Nefir that he wants weapons. When Aladdin is about to tell the Sultan another thing, Jasmine suggests that he should leave and tells him that her father has been ruler of Agrabah since before she and Aladdin were born. Aladdin walks away angry and says that his status dropped back to street rat. He then tells Genie to take Carpet and Iago and guard the palace to keep Jasmine safe while he and Abu go find Uncouthma.
When the Odiferans continue fighting Agrabah, Gouda asks Nefir for bigger weapons. Aladdin and Abu see that the imps built a giant metal ball, which rolls down the street, demolishing everything in its path. It then crashes into the tower Aladdin and Abu are in. The two jump to safety and continue finding Uncouthma. Nefir sees the two running toward the Odiferan camp and gets an idea. He goes to Uncouthma and tells him that Aladdin stole their Most Sacred Crock of Cheese. Uncouthma finds that hard to believe, but then accepts the leader of the imps' lie and decides to bash the street rat with a mace. Nefir tells the crocodile-headed imp to follow Uncouthma so that he can know everything that happened.
Meanwhile, the Sultan is waiting for Nefir to show up. Iago suggests that he has Genie defend Agrabah instead. Genie and Carpet turn into soldiers and the jinn makes Iago one as well. Nefir enters the palace and talks to them about Aladdin's "merry band" enlisting in Agrabah's army. Iago tells him that he's the soldier of fortune and Nefir decides that the parrot wouldn't volunteer to defend the city. Iago says that he loves to volunteer and Sultan tells him to fight Odiferous as well, even though the parrot didn't finish his sentence. Genie, Iago and Carpet are in a foxhole, fighting Odiferous. Genie later suggests that they find Aladdin.
Meanwhile, Aladdin and Abu arrive at the Odiferan camp. They then run into Uncouthma, who is about to bash Aladdin. The street rat tells him that he won't run away from him and he won't fight him either. He also tells the Odiferan prince that he will always be his friend no matter what happens. Uncouthma then decides that he shouldn't bash Aladdin. He then mentions Nefir to him and tells him that his imps built the weapons. Aladdin tells him that Nefir told them that he and the other barbarians were invading. Uncouthma then tells Aladdin that Nefir told him that he stole their Most Sacred Crock of Cheese. The crocodile-headed imp overhears everything and then goes to Nefir to tell him about it. Nefir then has a change of plans. He goes to Gouda and tells him that their "enemy" captured Uncouthma.
Gouda makes Nefir and his imps build another weapon. The Odiferan general is now driving a huge yak-drawn cart carrying giant battle tops. While Gouda's on his way to the palace, Nefir decides to have one more sale to the Sultan. Aladdin and Uncouthma see the giant tops. One of the Odiferans pulls a chain that causes one of the tops to spin off of the cart and go to the marketplace. Several more battle tops have later been released. Aladdin and Uncouthma destroy the tops and Genie, Iago and Carpet go to them. Everyone makes Iago fly to Jasmine so that she can tell her father that Nefir is behind the whole war.
Nefir goes to the Sultan and suggests that he uses a powerful, destructive and expensive weapon. Jasmine and Rajah are behind the curtain watching the Sultan and Nefir. Jasmine tells Rajah that she has never seen her father act like this. Iago flies over to Jasmine, but runs into a wall. Nefir and the Sultan enter a tower at the palace garden and two of Nefir's imps turn a wheel to lift it up. Nefir pulls a lever and it makes a bolt of electricity shoot out the top of the tower and blow up a minaret. Jasmine and Iago go to Nefir's imps and the Princess tells them to lower the tower. The imps laugh at her so she and Iago make Rajah chase them. Jasmine tries to turn the wheel, but it won't budge. Iago then pulls a lever and the tower falls back down. Nefir realizes what's going on and shoots a bolt of electricity at Aladdin's group, making a smoke crater be where Aladdin and Uncouthma were standing. Genie, having had enough calls for a ceasefire, allowing Jasmine and Gouda to run over to the crater.
Uncouthma climbs out of the crater carrying a motionless Aladdin. Jasmine tells Aladdin that he was right about Nefir and Aladdin regains consciousness, happy that Jasmine finally believes him. Everyone, including the Odiferans, are in the throne room and are furious with Nefir. It then smells like cheese in the throne room and Aladdin removes Nefir's tall hat and everyone finds the Most Sacred Crock of Cheese. Nefir tries to weasel his way out of trouble by saying peace is his buisness, but Gouda and the Sultan respectively demand that Nefir fix Agrabah right now and refund his gold. Nefir refuses, Until everyone, especially Aladdin, Genie, Uncouthma and Gouda all glare at him furiously.
The title is a pun on the title of the Barbara Streisand song "The Way We Were"