Η Αναστασία Αντρέγιεβνα (Andreeva) γεννήθηκε στο Βλαντικαβκάζ του Καυκάσου στην πλούσια οικογένεια εμπόρων, του Ανδρέα και της Ιουστινας Αντρέεβιτς (Ανδρέου). Είχε τρεις ακόμα αδελφούς. Η καταγωγή του πατέρα της ήταν ελληνική από την Κύπρο.
Μικρή την πάντρεψαν με έναν αξιοσέβαστο στρατηγό του τσαρικού στρατού, ο οποίος όμως έφυγε πολύ γρήγορα από την ζωή, αφήνοντάς την πολύ νέα χήρα. Οι γονείς της την πάντρεψαν για δεύτερη φορά με έναν χήρο όπου είχε δύο κόρες. Μένοντας χήρα για δεύτερη φορά, η Αναστασία δεν ξανασκέφτηκε πια τον γάμο.
Όλα αυτά έγιναν μέχρι την ημέρα που άγγελος Κυρίου της εμφανίστηκε σε όνειρο και της είπε: «Αναστασία, ακολούθησε τον Θεό!» Ο άγγελος δεν της εξήγησε τίποτα, έτσι η Αναστασία άρχισε να πηγαίνει την εκκλησία πιο συχνά, να προσεύχεται πιο θερμά και να ψάλλει στην εκκλησιαστική χορωδία.
Τον τέταρτο χρόνο της χηρείας της, άγγελος Κυρίου της εμφανίστηκε για δεύτερη φορά και της είπε: «Αναστασία, δώσε όλη σου την περιουσία σε όσους έχουν ανάγκη και ακολούθησε τον δρόμο του Θεού!». Αυτή τη φορά, χωρίς δισταγμό, μοίρασε όλη την περιουσία της -προς δυσαρέσκεια των αδελφών της- και πήγε στο γυναικείο μοναστήρι στο Vladikavkaz όπου έδωσε τον εαυτό της ολοκληρωτικά στον Θεό. Όταν αναχώρησε από το μοναστήρι, της ήταν ξεκάθαρο ότι αποχαιρέτησε για πάντα την κοσμική ζωή. Από εδώ και πέρα ήταν πιο φτωχή από τον πιο φτωχό άνθρωπο της πόλης.
Όταν για πρώτη φορά, η θαυματουργή εικόνα της Παναγίας των Ιβήρων μεταφέρθηκε από το Mozdok στο Vladikavkaz τότε εκδηλώθηκε η αγία μωρία, κι ότι η δια Χριστόν σαλότητα θα ήταν ο αγώνας της στο εξής.
Από τότε, διαδόθηκε ότι ο Θεός την επέλεξε ως μεσήτρια, ως ένα προσευχητάρι για όλους και της έδωσε το δώρο της προφητείας, αυτό μαθεύτηκε σε όλη την πόλη κι οι άνθρωποι άρχισαν να πηγαίνουν κοντά της.
Έμοιαζε ή ήταν ήδη μια ηλικιωμένη γυναίκα, καμπουριασμένη, κουβαλώντας συνεχώς ένα σακουλάκι με άμμο στην πλάτη της και κρατώντας πάντα ένα ραβδί στο χέρι της.
Για την πόλη του Βλαδικαυκάζ, η Αναστασία Αντρέγιεβνα έγινε η εκλεκτή του Θεού.
Πριν τελειώσει το επίγειο ταξίδι της, η Αναστασία πήγαινε από σπίτι σε σπίτι. Έμπαινε στην αυλή ή ανέβαινε στην εξώπορτα του σπιτιού και έλεγε: “Σύντομα θα γίνει πόλεμος!” Κοντοστέκονταν, και μετά πήγαινε σε άλλη πόρτα ή αυλή. Σχεδίαζε ένα σταυρό με ένα ραβδί, σκεφτική και λυπημένη. Όλοι γνώριζαν ότι στις πράξεις της υπάρχει πάντα ένας οιωνός για το μέλλον.
Κι όταν ξεκίνησε ο Μεγάλος Πατριωτικός Πόλεμος, σε εκείνα τα σπίτια όπου, σύμφωνα με τις αναμνήσεις των παλαιοτέρων ανθρώπων, η Αναστασία έκανε τους σταυρούς, εκεί υπήρξαν νεκροί.
Το 1942, οι Ναζί είχαν ήδη πλησιάσει το Βλαδικαυκάζ. Στην εκκλησία του Προφήτη Ηλία υπήρχαν στρατιώτες που φρουρούσαν τα σύνορα της πόλης. Ένα βράδυ είδαν στο νεκροταφείο όπου ήταν θαμμένη η μακαρία Αναστασία, μια γριά με μοναχικό ένδυμα με ένα παλιό όπλο. Περπατούσε γύρω από το νεκροταφείο. Οι στρατιώτες προσπάθησαν να τη σταματήσουν: «Φύγε, γιαγιά, από εδώ θα σε πυροβολήσουν!», κι αυτή απάντησε: « Εδώ δεν θα πυροβολήσουν, γιατί η γιαγιά Αναστασία δεν θα επιτρέψει στους Γερμανούς να πατήσουν τους τάφους.»
Μετά τον πόλεμο, διηγηθηκαν ότι οι τότε Ρώσοι στρατιώτες στέκονταν στην εκκλησία του Προφήτη Ηλία, περιμένοντας επίθεση και, καθώς άκουσαν κίνηση στο νεκροταφείο, νόμισαν ότι ήταν Γερμανοί. Αλλά αποδείχθηκε ότι ήταν μια γερόντισσα μοναχή με ένα μεγάλο σταυρό στο στήθος της και ένα ραβδί στο χέρι όπου ακουμπούσε. Όταν θέλησε να μπει στο ναό, οι στρατιώτες δεν την άφησαν. Τότε ζήτησε να συναντήσει τον διοικητή. Ο διοικητής βγήκε έξω και άρχισε να την ρωτάει ποια είναι και από πού έρχεται. Κι εκείνη του είπε: «Είμαι η Αναστασία, φυλάω την πόλη μας».
Ο διοικητής, δεν κατάλαβε καλά τι είπε και την ρώτησε: «Ποιο είναι το επίθετό σου;»
Η ηλικιωμένη γυναίκα συνέχισε: «Μη φοβάστε, όλοι θα μείνετε ζωντανοί».
Ο διοικητής ξαφνικά την έχασε, κοίταξε τριγύρω, η γερόντισσα είχε φύγει. Ρώτησε τους κατοίκους της πόλης, και του εξήγησαν ότι αυτή ήταν η προφήτισσα μακαριστή Αναστασία, και του έδειξαν τον τάφο της.
Αρκετές δεκάδες άνθρωποι προσεύχονταν στον τάφο της μακαρίας Αναστασίας το 1944 και όλοι τους είδαν ολοζώντανη την Θεοτόκο με τον Χριστό μας μωρό στην αγκαλιά της πάνω από τον τάφο. Ανάμεσα σε αυτούς που είδαν αυτό το όραμα ήταν και η μητέρα του σημερινού Πατριάρχης Γεωργίας Ηλία Β’. Σε αυτό το θαυμαστό γεγονός, 17 άτομα ήταν μάρτυρες.
Σύμφωνα με τις διηγήσεις μιας στρατιωτικού πιλότου, το μαχητικό της οποίας φλεγόταν κοντά στην πόλη, προσευχήθηκε: «Βοήθησέ με, μητέρα Αγία Αναστασία!» Το αεροπλάνο της κάηκε, αλλά αυτή επέζησε.
Πριν λίγο καιρό, οι ηλικιωμένοι κάτοικοι που ζούσαν ακόμα έλεγαν ότι κατά τον Μεγάλο Πατριωτικό Πόλεμο συνάντησαν την γερόντισσα Αναστασία, που κοιμήθηκε το 1932, στην πόλη αφού είχε περικυκλωθεί από τον γερμανικό στρατό. Ερχόταν από τον δρόμο του ναού του Προφήτη Ηλία. Την ρώτησαν: «Πού πας, μητέρα;» – κι η Αναστασία τους απάντησε: «Να προστατέψω την πόλη!». Και στην πρώτη γραμμή άμυνας της πόλης του Βλαδικαυκάζ εμφανίστηκε ολοζώντανη. Όπως γνωρίζετε, ο γερμανικός στρατός δεν μπόρεσε ποτέ να μπει στην πόλη, αλλά, αντίθετα, υποχώρησε με μεγάλες απώλειες. Όταν τελείωσε ο πόλεμος, όλοι οι στρατιώτες και ο διοικητής που βρίσκονταν τότε στο ναό, σύμφωνα με την πρόβλεψη της γεροντισσας, έμειναν ζωντανοί και γύρισαν σπίτι τους.
Κάθε χρόνο, για περισσότερα από τριάντα χρόνια, οι στρατιώτες και ο διοικητής τους έρχονταν από διάφορα μακρυνά μέρη στην εκκλησία του Προφήτη Ηλία για να προσκυνήσουν την μακαρία Αναστασία. Και όλοι πίστευαν ότι η Αναστασία έσωσε την πόλη της, ως προστάτιδα του Vladikavkaz.»
Τρία πράγματα άφησε η μακαριστή Αναστασία στους απογόνους της.
Το πλεκτό καπέλο που φορούσε. Το ραβδί στο οποίο ακουμπούσε και το κλειδί του κελιού της. Το καπέλο το κράτησε η οικογένεια Kanishchev, η οποία ήταν πολύ οικεία στην γερόντισσα και βρίσκεται στο Vladikavkaz.
Το ραβδί και το κλειδί τα κατέχει ο Πατριάρχης Γεωργίας Ηλία ο Β’ που γεννήθηκε και σπούδασε στην πόλη του Βλαντικαβκάζ. Ο Παναγιώτατος Ηλίας ο Β’ όταν έχει να λάβει δύσκολες αποφάσεις σε συνόδους του πατριαρχείου παίρνει πάντα μαζί του το ραβδί της αγίας Αναστασίας του Βλαδικαυκάζ.