Ayona is a city-state resembling late Victorian era-London. It was originally constructed centuries ago by gargoyles, magical creatures who can manipulate stone and rock but turn to stone fixtures at the ends of their lives. The first humans to settle in the city became the hereditary dukes who ruled at first, the gargoyles having little to do with humans after raising the stone foundations of the city and its buildings. Over time, the power of the dukes declined, and they were forced to share power with a parliament representing the factions of the Alchemists and Mechanics, each representing complementary facets of human creativity. In the past, the Alchemists were dominant, but by the time of the novel the Mechanics have taken the lead, and institute widespread economic and industrial innovations. The world outside the city is not described in great detail, other than there being a land of dark-skinned people across an ocean to the east, natives of whom have emigrated to the city to form a semi-oppressed minority group.

The main character is Mattie, a clockwork automaton constructed with a corset, petticoat and skirts, and heels built into her figure. Mattie is one of the few sentient automatons in the city, and was emancipated by her master, Loharri (one of the chief Mechanics) when she wished to study to become an Alchemist. However, even though technically emancipated, Loharri still holds the literal key to her heart, a unique key needed to wind up her mechanical heart, without which she will deactivate until it is wound again.

At the beginning of the story, Mattie is contacted by representatives of the last remaining gargoyles, who wish for her to use her skills to develop a method by which they can become mortal and escape their metamorphosis into stone. During her attempts to discover the technique to do so (the titular alchemy of stone), she crosses paths with Sebastian, an Easterner whose mother was a powerful stone alchemist. Sebastian himself became a Mechanic, only to leave the order due to their prejudice against him, joining a radical group aimed at overthrowing the existing social order which is being strained by the increasing adoption of new labor-saving technologies by the Mechanics, the latest development of which is the "Calculator", a steam-powered computer whose aim is to be able to guide the city along the most efficient path of development.

The radical group manages to bomb the parliament building and assassinate the duke, and a revolution breaks out. Industrial workers fired due to the use of labor-saving machines, miners who have been mutilated into grotesque forms by the Stone Monks (a corrupt religious order nominally serving the gargoyles but in reality aimed at self-promotion), and peasant farmers driven off their land by government industrialization are joined with disaffected groups of Alchemists, Mechanics, and Ducal courtiers. During the revolution, as the city they made is changed irrevocably, Mattie is able to finish her study of the alchemy of stone and grant the gargoyles their wish; however, during the fighting, Loharri is killed, and her key potentially lost or destroyed.

The novel ends on several ambiguous notes. The revolution succeeds, but with hints that the upper-class courtiers, Mechanics, and Alchemists who supported the rebels will once more take control from their working-class companions. Similarly, while Mattie succeeded in her quest to free to gargoyles and gain freedom from Loharri, without her key she winds down and deactivates. The novel ends with the gargoyles promising to spend the rest of their now-mortal lives in an attempt to find the key to restore their savior.

The novel was on the 2008 James Tiptree, Jr. Award Honor List^[1] and the Locus Recommended Reading List.^[2]

The novel was praised for how Mattie, despite her mechanical nature, captured the vulnerability and emotions of real women.^[3] Some reviewers noted that the scenes where the parliament building is bombed and the aftermath evoked memories of the September 11 attacks.^[4]

• Review from Locus Online
• Interview from Fantasy Magazine
• Review from io9