Maria wsiada do pociągu, lecz jej wnuczce się to nie udaje – pada ona na peron bez przytomności.

Po 10 latach Anastazja (posługująca się imieniem Ania) wychodzi z sierocińca, jednak nie pamięta nic ze swojej przeszłości. W towarzystwie przyjaznego psa imieniem Mucha rusza do Sankt Petersburga, gdzie kierując się napisem na naszyjniku usiłuje kupić bilet do Paryża, licząc na odnalezienie tam swoich bliskich. Potrzebna jest jej do tego wiza, więc Ania udaje się do opuszczonego carskiego pałacu, gdzie podobno przebywa ktoś, kto może jej taką załatwić. Są to Dymitr i jego przyjaciel Wołodia, upadły arystokrata – drobni oszuści, którzy znęceni nagrodą oferowaną przez Marię usiłują odnaleźć kogoś przypominającego Anastazję, zwrócić ją babce w Paryżu i zgarnąć pieniądze, zanim ta się zorientuje. Anię w pałacu nękają niejasne wspomnienia.