Warning: Wikipedia contains spoilers.
On a visit to the castle of the sorceress Glinda in the Quadling Country, Ozma and Dorothy discover a reference in Glinda's Great Book of Records to a war about to begin between the Skeezers and the Flatheads, two peoples of the Gillikin Country of Oz. Glinda's magic can find out very little about them. Ozma decides that it is her duty as ruler of Oz to stop the fighting if she can, and she and Dorothy choose to travel there after being supplied from the Emerald City. Glinda anticipates trouble, so she gives Dorothy a ring to signal her if she and Ozma are in great danger.
On their journey Ozma and Dorothy escape giant purple spiders and arrive at Flathead Mountain where the inhabitants are, in keeping with the name, flat-headed. The Su-Dic (Supreme Dictator) explains that each Flathead carries their brains in their pockets, and they are going to war with the Skeezers because their queen, Coo-ee-oh, used magic to transformed the Su-Dic's wife, a witch named Rora, into a golden pig and refuse to allow the Flatheads to catch fish in their lake. The Su-Dic's belligerence prompts Ozma to turn herself and Dorothy invisible so they can escape north to the glass island of the Skeezers. A steel bridge magically extends from the island on the lake and Dorothy and Ozma are ushered into the presence of Queen Coo-ee-oh, who seems to welcome war with the Flatheads as much as the Su-Dic does with the Skeezers. Since the steel bridge has been retracted, Dorothy and Ozma cannot leave the island and Coo-ee-oh has them kept in a minimum security prison until the war is over.
Dorothy and Ozma learn from the Queen's chambermaid Aurex that the trouble really began when Coo-ee-oh, who had been taught the rudiments of magic by three Adepts at Magic who ruled the once-friendly Flatheads, used what she'd learned to transform the Adepts from women into fish in the Skeezer lake. The Su-Dic and Rora saw their chance to take over the Flatheads themselves, stealing brains from their fellows. Coo-ee-oh also used magic to institute a reign of terror over the Skeezers; she can hear everything spoken on the island and can swiftly punish any sedition.
The next morning, Coo-ee-oh magically lowers the Skeezers' island beneath the surface of the lake and sends soldiers in submersible boats to attack the invading Flatheads. But the Su-Dic catches Coo-ee-oh by surprise and transforms her into a swan with no memory of her past life. In his joy, the Su-Dic knocks over the poison he intended to use on the Skeezer lake (which would have killed the Adepts, the remaining threat to his rule). But he leaves victorious because he knows that the Skeezer soldiers are stranded on the lake's surface and the Skeezer people in the city can't raise it to the surface without Coo-ee-oh's magic. Dorothy twists the ring Glinda gave her and the sorceress calls a Council of State to go with her from the Emerald City to the Skeezer island.
One of the queen's soldiers, a boy named Ervic, is whispered to by the Adepts at Magic in their fish forms and encouraged to take them to Reera the Red, an isolationist witch who specializes in transformations. Through cunning and reverse psychology, the Adepts succeed in having Reera restore them to their rightful forms. Meanwhile, Glinda and the party from the Emerald City try to dredge the lake and raise the island by magic, but their attempts fail until some of the party is actually lowered within the city to examine it and its intricate machinery. The machinery can only be moved by magic, and Glinda discovers that Coo-ee-oh used a magic powder to perform some of her greatest feats. Dorothy deduces that the former Skeezer queen would have needed three magic words regarding the island: one to release the submersible boats, one to extend the bridge, and one to raise and lower the island. And her name, Coo-ee-oh, has three words. So through trial and error, the party raises the island by burning some of the magic powder and uttering "Oh".
The Skeezers along with the Oz people celebrate their victory (in the first documented celebration that doesn't take place in the Emerald City) and name Aurex queen, who appoints Ervic Prime Minister on the recommendation of the restored Adepts. The party from the Emerald City and the Adepts return the Flathead mountain, where they are warmly welcomed by all except the Su-Dic -- but once his extra cans of brains are removed, he's harmless. Glinda performs an enchantment on each Flathead that allows the tops of their heads to grow around their brains, thus giving them round heads. They rename themselves Mountaineers and accept the rule of the Adepts once again. Both they and the Skeezers pledge themselves henceforth to be loyal subjects of Ozma.