«Бессмертный» — история Марьи Моревны и Кощея Бессмертного в России ХХ века. Маша — младшая из четырех сестер, живущих в Петрограде. Она видит, как ее сестер одну за другой уносят из дома птицы: они бьются в окна и в двери, падают оземь, оборачиваются солдатами и обручаются с девушками. Когда Советы национализируют дом и вселяют в него одиннадцать семей, Маша становится дочерью двенадцати матерей, и птица за ней не прилетает, зато домовой приводит Машу в Комитет домовых, который решает, как управлять домом. По совету домовых Маша разыскивает ведьму, которая дает девушке книгу и велит найти гребень, который в конечном итоге приведет к Маше суженого.
Но ее суженый — не солдат, это сам Кощей Бессмертный, царь жизни. Он уносит Машу через степи в свое царство, где идет вечная битва между братьями — царем жизни и царем смерти. Маша становится наложницей Кощея и мечтает о том, чтобы стать царицей, однако прежде ей предстоит завершить подвиги Бабы Яги, сестры царя жизни, ныне именующей себя Председательницей Ягой...