Η ιστορία της αυτοκράτειρας Αναστασίας είναι ένας από τους πιο σταθερούς θρύλους της ιστορίας. Αυτό που έχει σημασία λένε οι δημιουργοί είναι το να πιστεύει ο κόσμος σε ρομαντικές ιστορίες. Όπως και σε ιστορίες ειδυλλίων και σπαρακτικών επανασυνδέσεων. Η θρυλική ιστορία της Αναστασίας ξεκινά ακριβώς από τη στιγμή της εκτέλεσης της τσαρικής οικογένειας από τους μπολσεβίκους το 1918. Σύμφωνα με ένα μύθο που επικράτησε εκείνη την εποχή η Αναστασία επιβίωσε και απέδρασε στη Δύση.
Τουλάχιστον δέκα γυναίκες στη συνέχεια ισχυρίστηκαν ότι ήταν η μεγάλη Δούκισσα. Η διασημότερη αυτών ήταν η Άννα Άντερσον, η οποία ισχυρίστηκε πώς προσποιήθηκε την νεκρή ανάμεσα στα σώματα της οικογένειάς της και κατάφερε να διαφύγει χάριν σε έναν πονόψυχο φρουρό που την λυπήθηκε. Δύο άλλες νεαρές γυναίκες υποστήριξαν πως ήταν η Αναστασία και η αδερφή της Μαρία και μεταφέρθηκαν από έναν ιερέα στα Ουράλια Όρη το 1919 όπου και έζησαν ως μοναχές μέχρι το θάνατό τους το 1964. Τάφηκαν με τα αυτοκρατορικά ονόματα Αναστασία και Μαρία Νικολάγιεβνα.
Οι φήμες σχετικά με την επιβίωση της Αναστασίας βασίστηκαν σε διάφορες αναφορές της εποχής που υποστήριζαν ότι οι μπολσεβίκοι έψαχναν τρένα και σπίτια προκειμένου να βρουν τα ίχνη της. Αυτόπτες μάρτυρες στο Περμ ισχυρίζονταν ότι έβλεπαν την Αναστασία και άλλα μέλη της αυτοκρατορικής οικογένειας. Και ένας ιστορικός της εποχής καταγράφει τη σύλληψη μιας νεαρής γυναίκας που προσπαθούσε να αποδράσει στον σιδηροδρομικό σταθμό της ίδιας πόλης. Η νεαρή γυναίκα τραυματίστηκε και λένε ότι όταν ρωτήθηκε είπε: «Είμαι η κόρη του κυβερνώντος, η Αναστασία». Ήταν μια ιδιαιτέρως ταραγμένη εποχή όπου πολλά άτομα ταξίδευαν ως φυγάδες Ρομανώφ. Ο Μπόρις Σολόβιεφ, σύζυγος της κόρης του Ρασπούτιν, Μαρίας, εξαπάτησε επιφανείς ρώσικες οικογένειες ζητώντας χρήματα για να διαφύγει κάποιος σωσίας των Ρομανώφ στην Κίνα. Ο ίδιος έψαχνε νεαρές γυναίκες πρόθυμες να υποδυθούν μια από τις κόρες του Τσάρου για να εξαπατήσει αυτές τις οικογένειες.
Καθώς η φήμη για την επιβίωση της Αναστασίας αποτελούσε ένα από τα διασημότερα μυστήρια της εποχής, το 1922, μια γυναίκα, που συστήθηκε ως Άννα Άντερσον, εμφανίστηκε στη Γερμανία και υποστήριξε πως ήταν η Αναστασία. Πυροδότησε διχογνωμίες μέχρι και το τέλος της ζωής της και εμφανιζόταν στους τίτλους των εφημερίδων για δεκαετίες, με κάποιους από τους συγγενείς της Αυτοκρατορικής Οικογένειας που ήταν ακόμη εν ζωή να την πιστεύουν, ενώ άλλοι όχι.
Η Άννα Άντερσον έδωσε στο μύθο της Αναστασίας τη μεγαλύτερη διασημότητα που θα μπορούσε να έχει. Η μάχη της για την αναγνώρισή της ως Αναστασία από τα γερμανικά δικαστήρια εξακολουθεί να είναι η μεγαλύτερη σε διάρκεια εκδίκαση υπόθεσης που έγινε ποτέ. Ξεκίνησε το 1938 και η απόφαση βγήκε το 1970. Το δικαστήριο αποφάνθηκε πως η Άντερσον δεν παρείχε αρκετές αποδείξεις για να διεκδικήσει την ταυτότητα της Μεγάλης Δούκισσας. Ανάμεσα σε άλλα, επίσης το δικαστήριο δεν αναγνώρισε το θάνατο της Αναστασίας σαν επιστημονικά τεκμηριωμένο ιστορικό γεγονός.
Το 1994 διεξήχθη τεστ DNA σε δείγμα ιστού της Άντερσον που υπήρχε σε ένα νοσοκομείο και σε αίμα του Πρίγκιπα Φιλίππου, στενού συγγενή της Αυτοκράτειρας Αλεξάνδρας. Σύμφωνα με την εξέταση δεν υπήρχε συγγενική σχέση ανάμεσά τους.
Το 1991, σώματα που θεωρείται πως ανήκουν στην Αυτοκρατορική Οικογένεια και στους υπηρέτες της βρέθηκαν τελικά σε ομαδικό τάφο στο δάσος έξω από το Αικατερίνενμπουργκ. Ο τάφος είχε ήδη ανακαλυφθεί μια δεκαετία νωρίτερα, μα διατηρήθηκε μυστικός, καθώς ο Κομμουνισμός κυριαρχούσε ακόμη στη χώρα. Αντί για τα έντεκα σώματα που έπρεπε να είναι θαμμένα, βρέθηκαν εννιά. Ο σκελετός της έφηβης Αναστασίας και του Αλεξέι έλειπαν, κάτι που επιβεβαίωσαν οι Ρώσοι επιστήμονες. Τα λείψανα τράφηκαν το 1998 και το 2000 η Αναστασία και η οικογένειά της αγιοποιήθηκαν σαν μάρτυρες από τη Ρωσική Ορθόδοξη Εκκλησία. Η αγιοποίησή τους προκάλεσε αντιδράσεις καθώς δεν θανατώθηκαν εξαιτίας της πίστης τους.
Η φημολογούμενη απόδραση της Αναστασίας έχει αποτελέσει αγαπημένο θέμα έργων του κινηματογράφου και της τηλεόρασης. Η πρώτη από αυτές, γυρισμένη το 1928, ονομαζόταν Clothes Make The Woman. Αφορούσε μια γυναίκα που επρόκειτο να εμφανιστεί σε μια χολιγουντιανή ταινία στο ρόλο της Αναστασίας και την οποία τελικά αναγνώρισε ο Ρώσος στρατιώτης που την έσωσε από τους επίδοξους δολοφόνους της.
Η πιο διάσημη εκδοχή της ιστορίας στο σινεμά, είναι η ταινία του 1956 με τίτλο «Αναστασία» με την Ίγκριντ Μπέργκμαν στο ρόλο της Άννας Άντερσον. Το φιλμ αφηγείται την ιστορία μιας γυναίκας από ένα άσυλο που κάνει την εμφάνισή της στο Παρίσι το 1928 και που εκπαιδεύεται από Ρώσους πολιτικούς πρόσφυγες για να ξεγελάσει τη γιαγιά της Αναστασίας, Αυτοκράτειρα Μαρία, ώστε να πιστέψει πως είναι η εγγονή της και να κληρονομήσει την αμύθητη περιουσία των Τσάρων. Καθώς περνά ο καιρός, τα γεγονότα τους πείθουν πως αυτή η γυναίκα είναι πράγματι η Μεγάλη Δούκισσα. Η ιστορία αυτή αποτέλεσε τη βάση για το βραχύβιο μιούζικαλ του 1965 με τίτλο Anya.
Η πιο πρόσφατη ταινία παρουσιάστηκε το 1997. Πρόκειται για ένα μιούζικαλ κινουμένων σχεδίων με τίτλο Αναστασία, από την εταιρία Twentieth Century Fox. Η ιστορία είναι επίσης βασισμένη σε πραγματικά γεγονότα, αντικείμενα, κοστούμια και τοποθεσίες, ωστόσο δεν μένει αυστηρά πιστή στην ιστορική αλήθεια. Παρουσιάζει τις περιπέτειες μιας νεαρής κοπέλας, την οποία εκπαιδεύουν δύο απατεώνες προκειμένου να φέρεται και να συστήνεται ως Αναστασία, ώστε να εισπράξουν μια τεράστια αμοιβή από τη γιαγιά της. Στην νέα παραγωγή του Μπρόντγουέι τους βασικούς ρόλους θα υποδυθούν η Christy Altomare (Anya και ο Derek Klena (Dmitry).