The novel begins with Abdullah, a young carpet merchant living in a baazar in the city of Zanzib. He buys a carpet from a man, who claims that the carpet is magical. Abdullah then finds that the carpet is a magic carpet and takes him to places that replicate his dreams (since he dreams of being a long lost prince). He finds himself in a garden with a lovely woman. He introduces himself. The girl mistakes him for a woman. She then introduces herself as Flower-in-the-Night, daughter of the Sultan of Zanzib. She has been raised in seclusion due to a prophecy that she would marry the first person she meets other than her father. Abdullah brings her pictures of men. When he next arrives, Flower-in-the-Night is kidnapped by a djinn. He is then captured by the Sultan of Zanzib who thinks Abdullah kidnapped his daughter, since he doesn't believe in djinn. He throws Abdullah in the dungeon. Abdullah is lucky to escape with his life when the carpet arrives with Jamal's dog on it.
Flight Through the Desert
When walking across the desert, he meets a gang of thieves who have a bottle containing a bad tempered genie who will grant only a single wish a day. After a wish, Abdullah is transported to the land of Ingary (the setting of the previous book) and meets a soldier who claims to be from Strangia while he is at a pub. He then finds out that he is in Ingary.
Midnight and Whippersnapper
The soldier finds two cats called Midnight and Whippersnapper. He insists on keeping them, much to Abdullah's dismay. Abdullah and the soldier are both framed for assault and robbery. Abdullah tells the magic carpet to bring back the djinn who kidnapped Flower-in-the-Night. It is revealed that the djinn is called Hasruel and is being forced to kidnap princesses around the world by his brother, Dalzel because Dalzel has stolen and hidden his "life." He then tells Abdullah and the soldier that they will help him steal Princess Valeria, and flies away laughing.
They arrive at Kingsbury, where they find an inn to stay at. Abdullah leaves the soldier in the inn with Whippersnapper and the genie, and walks to the Royal Wizard's home to warn him of the threat of the djinn. He briefly notices Midnight following him. When he arrives at the Royal Wizard's home, Abdullah meets Lettie Suliman, the Wizard's pregnant wife, and Midnight causes a commotion by leaping onto Lettie's chest. Abdullah meets Wizard Suliman. It is also revealed that Midnight is Sophie Hatter and Whippersnapper is her son Morgan. The djinn also kidnaps Morgan but steals Valeria. Abdullah and Sophie travel to the castle in the sky. Sophie tells Abdullah about her husband, Howl.
Castle in the Air
When they arrive at the castle, Sophie reveals that it is Howl's castle. They then meet the princesses and Princess Valeria.
Dalzel sees Abdullah and threatens to send him down to earth. Led by Abdullah, the princesses overpower the djinn. Hasruel sends his brother into exile. The genie is revealed to be Howl and that Dalzel ordered Hasruel to steal the castle from them. It is also revealed that the magic carpet is really Calcifer.
The King of Ingary promotes both Abdullah and Flower-in-the-Night to Ambassadors and gives them their own house in the Chipping Valley.
- Abdullah- a young carpet merchant and the main character of the story. He often daydreams. One of his most common daydreams is imagining himself as a long lost prince from a faraway land.
- Flower-in-the-Night- the daughter of the Sultan of Zanzib. She was raised in seclusion because of a prophecy that said she would marry the first man she laid eyes on.
- Dalzel- the main antagonist. An evil djinn who forces his brother to steal princesses to be his wives.
- The Soldier
- Sophie Hatter
- Howl Jenkins Pendragon
- Sultan of Zanzib
- Princess Valeria
- Wizard Suliman
- Princess Beatrice- Very strong minded. Ran away from home to avoid marrying Prince Justin of Ingary.
- Princess of High Norland
- Princess of Tsapfan- Looks after Morgan while he is in the Castle in the Air. Claims to have born twelve children, all boys. She has an accent which makes it hard to understand what she says.