Fourteen-year-old Matt Cruse is a cabin boy for the Aurora , an airship that stays afloat using a gas called "hydrium". While on lookout duty, he spots a damaged balloon carrying an unconscious old man. The Aurora's crew mount a rescue operation to save the man, whose name is later said to be Benjamin Malloy. Malloy rambles about "beautiful creatures" and dies shortly after being taken aboard.
One year later, Matt leaves his home in Lionsgate City to accompany the Aurora on its voyage to Sydney, Australia. Despite loving his mother and sisters dearly, Matt is relieved to be in the air where he feels closest to his father — a former sailmaker who died in an accident aboard the Aurora. Matt is disappointed to learn that the Junior Sailmaker position he was promised has been given to the fleet's owner's heir, Bruce Lunardi. One day into the voyage, an ornithopter delivers two passengers to the ship: Kate de Vries and her chaperone Marjorie Simpkins. Kate tells Matt that she is Benjamin Malloy's granddaughter and shows him detailed drawings of flying panther-like creatures from Malloy's journal. Intrigued by the possibility that they live their whole lives in the air, Kate reveals that she is on a mission to prove that such creatures are real.
A few nights later, the ship is raided by a notorious criminal named Vikram Szpirglas. His gang of pirates plunder the ship of all valuables and kill the chief wireless officer. The pirates proceed to leave, but both ships are caught in a storm which produces a tear in the Aurora's hull, in effect depleting its supply of hydrium. As the sailmakers scramble to repair the falling Aurora, Matt spots an island and the crew steers toward it. The ship crash lands on the island, which to Kate's realization, is the island from her grandfather's journal. Kate convinces Matt to help her explore the island where they discover the skeleton of a large winged creature. A few minutes later, they find an injured member of the same species which they decide to call a "cloud cat". During the journey, Matt smells a mango-like scent, which he later realizes indicates the presence of hydrium on the island.
Miss Simpkins tries to lock Kate in her room for associating with Matt. As the repairs near completion, Kate drugs her and takes one last chance to photograph the island's wildlife. Matt and Bruce begin looking for her until Bruce suffers a bite on his leg from a cloud cat. Matt is able to find Kate, but the two of them stumble upon the pirates at one of their encampments. Unrecognized, they ask for shelter in the pirate camp and make a plan to sneak away during the night. During their escape, Kate and Matt are apprehended and thrown into a hydrium pit where there is no oxygen. They use Kate's harem pants as a balloon to lift themselves to ground level as Szpirglas' crew sets out to silence the passengers of the Aurora. Kate begins crying in the forest, blaming herself for putting everyone else in danger. Acting on the feelings he has developed for her, Matt kisses her.
Once Kate and Matt find Bruce, the three make their way to the Aurora, which is being held hostage by eight pirates. They are able to undo the landing lines and cause the ship to take off. Matt's innate knowledge of the flight system allows them to temporarily take control and steer the ship away from the island. After tending to Bruce's wounds in the infirmary, Matt brings a sleeping elixir to the cook so that it can be added to the pirates' soup. Szpirglas' crew murders Bruce in the engine room and chases Matt onto the hull of the Aurora in open air. Szpirglas pushes Matt off the edge; luckily, he is able to grab a hold on the ship's tail fin. Just as Szpirglas is about to kill Matt, he is attacked by a group of cloud cats and is thrown into the sea. The passengers are saved when Matt steers the Aurora back on course.
Six months later, Matt meets Kate in Paris, where she is exhibiting her cloud cat skeleton and photographs. Matt reveals that he will attend the Airship Academy, with the help of the reward money for finding Szpirglas' base of operations. Kate plans to begin her zoology studies at a university.