The novel is set in an alternate Victorian England where vampires, werewolves, and steam-powered mechanicals (robots) are part of everyday life. Fourteen-year-old Sophronia Temminnick, one of several children in a gentry family, is a perpetual source of embarrassment to her mother. When she crashes out of the household dumbwaiter and launches a trifle onto the head of Mrs. Barnaclegoose, a visiting society matron, her mother seizes the opportunity to enroll her in Mademoiselle Geraldine's Finishing Academy for Young Ladies of Quality. A crowlike woman posing as the headmistress tests Sophronia's reflexes, strength, and capacity for deception before whisking her away in a carriage.
In the carriage, Sophronia meets Dimity Ann Plumleigh-Teignmott, a chatty girl of about 13, and Dimity's younger brother Pillover, a bookish boy bound for Bunson and Lacroix's Boys' Polytechnique, a school that trains evil geniuses. Dimity hints that the finishing school is not what it seems and calls Sophronia a "covert recruit" with no family ties to the institution. Before she can explain further, flywaymen, sky-based highwaymen operating from a balloon-lifted airship called an airdinghy, ambush the carriage and demand a mysterious "prototype." Sophronia takes action: She climbs atop the carriage, burns through the airdinghy's mooring rope using Pillover's magnification lens, commandeers the horses, and drives back to rescue the supposed headmistress. Dimity sustains a bullet graze during the escape.
After the rescue, the supposed headmistress drops her French accent and reveals herself to be Monique de Pelouse, an older student on a "finishing assignment," a final exam requiring her to impersonate the headmistress and retrieve both new students and the prototype. The group travels across Dartmoor, and the school turns out to be a massive airship: three dirigibles lashed together, floating above the moor.
Captain Niall, a young man who transforms into a werewolf, carries each girl up to the ship on his back. Aboard, Sophronia meets the teachers: Lady Linette de Limmone, who teaches espionage; Sister Mattie, a nun who covers poisons; and Professor Lefoux, a Frenchwoman who handles weaponry. Monique lies to the teachers, claiming she rescued the group and that Sophronia panicked. She refuses to reveal where she hid the prototype, using it as leverage for her graduation, and Professor Lefoux demotes Monique to debut status as punishment.
Sophronia meets the real Mademoiselle Geraldine, a kind woman oblivious to the school's true espionage curriculum, and Professor Braithwope, a dapper vampire in a crimson top hat who teaches history and etiquette. That night, flywaymen return and threaten to come back in three weeks for the prototype. Professor Lefoux and Professor Braithwope begin planning to build a fake. During the commotion, Sophronia secretly pockets a small sausage-dog-shaped mechanimal (mechanical animal) she names Bumbersnoot. She then strikes a bargain with Monique: She will not contradict Monique's lies about the rescue if Monique stays quiet about the stolen mechanimal.
Her fellow debut students include Preshea Buss, a beautiful but mean-spirited girl; Agatha Woosmoss, a shy redhead; and Sidheag Maccon, Lady Kingair, a tall Scottish girl raised by her great-great-great-great-grandfather's werewolf pack. Through conversations with these girls, Sophronia pieces together the school's true purpose: training young women as intelligencers, or spies, and possibly assassins, under the cover of a conventional finishing school.
Lessons follow unconventional "London hours," running from noon into the early morning, and blend etiquette with espionage. When Professor Lefoux's attempt to build a fake prototype explodes, Sophronia collects a sample of the residue. She begins exploring the ship's exterior and discovers the boiler room, where she befriends Phineas B. Crow, known as Soap, a genial Black sootie (coal shoveler) who provides coal for Bumbersnoot. On a nighttime trip, she meets Genevieve Lefoux, called Vieve, Professor Lefoux's nine-year-old niece who dresses as a boy and carries a wrist-mounted device nicknamed "the obstructor" that can temporarily freeze mechanicals.
During a weapons lesson on the moor, Sidheag impresses everyone with combat skills honed by her werewolf guardians. Monique demonstrates a different approach by flirting with Captain Niall and then stabbing him with a sharpened stick. Sophronia learns that Monique has an unknown advocate among the teachers, explaining her continued leverage over the staff.
A second flywayman attack brings a larger fleet backed by Picklemen, a shadowy organization that collects money and power. The school's middle balloon is damaged by cannon fire before Lady Linette orders surrender and Professor Lefoux hands over the fake prototype. Sophronia spots a mysterious gentleman with a green-ribboned top hat observing from one of the dirigibles.
While the school attends a play in the nearby town of Swiffle-on-Exe, Sophronia, Vieve, and Soap sneak off and infiltrate Bunson's to examine the communication machine the prototype is designed to complete. They discover it is an experimental device for point-to-point messaging through the aethersphere (the upper atmosphere), which would revolutionize long-distance communication. The missing prototype is a multifaceted valve that enables this transmission. On the return trip, they narrowly escape Captain Niall in his uncontrolled full-moon werewolf form.
The school retreats deep into Dartmoor's mists, "going gray," for three months, cutting off all outside communication. During this isolation, Sophronia realizes Monique must have hidden the prototype at the Temminnick family home during the brief window when she toured the grounds while posing as headmistress. Sophronia forms a study group with Dimity, Sidheag, and Agatha, and the four resolve to find the prototype themselves after Monique escalates her bullying. To identify who recommended her recruitment, Sophronia, Dimity, and Soap break into the school's record room and discover that Mrs. Barnaclegoose is a graduate of the academy.
When the school exits the gray for winter break, Monique threatens Sophronia with a sharpened hair stick to the throat. Sophronia, Dimity, Pillover, and Monique travel to the Temminnick estate. At the coming-out ball for Sophronia's sister Petunia, Sophronia and Dimity shadow Monique, who slips into the garden and retrieves the prototype from the hollow pedestal of a birdbath. A government representative and the green-ribboned Pickleman both confront Monique, each demanding the device, while the Pickleman summons a massive mechanical bulldog. Using the chaos of a scuffle between Pillover and the Pistons, a Bunson's boys' club, as cover, Sophronia rips Monique's dress to force her to drop her bag, swaps the prototype for a cheese pie, and feeds the real device to Bumbersnoot's internal storage compartment.
Sophronia finds Mrs. Barnaclegoose inside and entrusts Bumbersnoot, with the prototype in his belly, to the retired intelligencer for delivery to the proper authorities. Monique, discovering the switch, storms into the ballroom in her tattered undergarments and hurls the cheese pie at Sophronia's head. Mrs. Temminnick, horrified by the destroyed gazebo and her daughter's cheese-covered state, insists Sophronia return to finishing school. Back at Mademoiselle Geraldine's, Sophronia finds a commendation in her record, the prototype safely delivered to Bunson's for reproduction, and a note pinned to Bumbersnoot from Mrs. Barnaclegoose requesting a more genteel method of object transfer in the future.