Marya Morevna and her sisters live with their upper middle class parents in Saint Petersburg before and during the Russian Revolution. Marya witnesses birds transform into handsome young men who marry her sisters, and meets the council of domovoi or brownies who live in her house along with the other families that get assigned to live there by the Bolsheviks, and cherishes her secret knowledge that magic exists in the world. She also meets an old woman named Likho who teaches her the mythology of the world, and of the Tsars and Tsarinas who rule various aspects of reality such as life, death, salt, night, water, birds and the length of an hour, of which Likho is one: the Tsarina of the Length of an Hour, who commands misfortune and sorrow. In time, Koschei the Deathless, who cannot die because he has cut out his death and hidden it in an egg, comes to marry her and takes her away from wartime Leningrad to the isle of Buyan in the Country of Life where he lives in luxurious splendour.

While in Buyan, Marya makes three companions of the magical creatures who live there: a vintovnik (or gun-imp) named Nastya, a leshi called Zemlya, and a vila called Lebedeva. When Koschei's sister Baba Yaga, the Tsarina of Night, sets Marya three tasks before she is allowed to marry Koschei in the traditional manner of a fairytale, each of these companions helps her complete one task with their powers. In the process, she learns that Koschei has had countless wives before, usually named Yelena or Vasilisa – the stock fairytale heroines of Russian folklore who defy Koschei and steal his death and run away with princes named Ivan – whom he keeps in an enchanted stupor, and vows to do better than them. Baba Yaga begrudgingly blesses Marya's union with Koschei and marries them, but not before Viy, the Tsar of Death, interrupts the ceremony and attacks Buyan, killing Marya's companions in the process.

Over the next several years, Marya and Koschei wage a supernatural war against Viy, until one day a young human named Ivan Nikolayevich – himself a version of the stock character of Ivan Tsarevich – comes across Marya's campaign tent in the midst of a battlefield. Marya brings him back to Buyan and they become lovers, running away from Koschei together back to Leningrad with the help of Marya's elder sisters, to Marya's old house where they live together as husband and wife. World War II comes to Russia, and slowly Marya and Ivan's marriage becomes unhappy in the midst of their hardship. Koschei appears on Marya's doorstep one day, weeping and begging her to take him back, and she ties him up in the cellar while he confesses his lies and sins to her. Starving during the Siege of Leningrad, Ivan becomes convinced that Marya is hiding food in the cellar, but when he goes down he finds only Koschei, who tricks Ivan into giving him a drink of water. This restores Koschei's magic, and he flies out of the cellar and takes Marya away.

After this follows an interlude where Marya and Koschei live in an alternate version of a Russian village in the woods, along with innocent, happy villagers who are alternate versions of Tsar Nicholas II and his family, Rasputin, and Josef Stalin and Leon Trotsky. Eventually, Marya falls pregnant and gives birth to a daughter by Koschei, who embodies his death. She kills him, and Marya awakes in the nest of Alkonost, the Tsar of Birds, who explains that the village of Yaichka in which she has lived with Koschei was a dream inside an egg laid by Alkonost that contained two things: the death of Koschei the Deathless, and a world without sorrow. Alkonost returns Marya to the world of men where she arrives home to find Ivan dying of starvation in their old house. He professes his love to her and asks her forgiveness before dying, and Marya leaves Leningrad and joins the Red Army.

Years later, she comes upon a village that she seems to recognise, and realises that it is almost exactly like a mundane version of Buyan, with human versions of her old magical companions, and a woman named Yelena who claims to be married to Koschei. Baba Yaga is also there, and seems to be the only person who recognises Marya or remembers Buyan or the world when it was magical, and explains to her that the Tsar of Death won the war, and now the whole world is the Country of Death, and all the mystical and mythical and fairytale things of old Russia have become mundane and everyday and no longer remember their existence in the world before, for the Revolution and the two wars have brought about a process of disenchantment that has affected all of Russian culture.

The story ends on an ambiguous note, with Marya Morevna resolving to explore the village of Buyan that night and find Koschei and see if he remembers her and knows who she is.

The A.V. Club complimented Valente's prose, comparing it favorably to her previous works — in particular, her 2009 novel Palimpsest — and said that thematically, Deathless "does for Russia what Susanna Clarke's Jonathan Strange & Mr Norrell does for England".^[2]

Strange Horizons's Erin Horáková similarly praised Valente's use of language, while criticizing the novel's plot as being "something of a mess", and that it "wants to say so much that it's difficult to hear it saying anything in particular". Horáková concluded, however, that Deathless "reveals more about the writer's technique and strengths than a polished, impregnable work might."^[3]

• Magyarody, Katherine (2017). "Translating Russian Folklore into Soviet Fantasy in Arkadi and Boris Strugatski's Monday Begins on Saturday and Catherynne M. Valente's Deathless". Marvels & Tales. 31 (2): 338–369. doi:10.13110/marvelstales.31.2.0338. S2CID 191746397.

• Deathless on ISFDB: [1]
• Deathless in the Library of Congress online catalog: [2]