Catherynne M. Valenteová v Nesmrtelném příběhu vychází z dobré znalosti ruských pohádkových motivů. Nejen motivicky, ale i po jazykové stránce Nesmrtelný příběh připomíná nejlepší díla magického realismu ve své nejčistší podobě (připomeňme v této souvislosti například povídkovou tvorbu Maxima Gorkého). Marija Morevna, hlavní hrdinka románu, už jako dítě objeví bránu do světa kouzel, a tím navždy určí svůj osud. Stojí tak po celý život rozkročena mezi dvěma světy – realitou Ruska první poloviny 20. století a říší Života Kostěje Nesmrtelného. Ale ať už mezi rusalkami, obry a domy spletenými z lidských vlasů a kůže, nebo s přídělovými lístky v ruinách bombardovaného Petrohradu, zakouší Marija Morevna sílu pravé lásky, bolest z osudových ztrát, chvilkovou opojnost štěstí, nesnadnou volbu mezi Dobrem a Zlem a nevyhnutelnost osudu – prožívá svůj nesmrtelný příběh.