Anastasia Konstantinóvna Prijodko (Kiev, 21 de abril de 1987) es hija del minero ruso Konstantin Rybalv y la periodista ucraniana y crítica de teatro del Ministerio de Cultura, Oksana Mikhaylovna. La madre incita a su hija desde pequeña al aprendizaje musical, igual que a su hermano mayor, el cantante y compositor Nazar Prijodko. Así, aprende piano, flauta y guitarra en el Instituto Nacional de la Cultura y las Artes de Kiev, antes de interesarse por la voz que desarrolla como contralto en la Escuela R. Glier, siguiendo un estilo popular profundamente arraigado en la voz de pecho. Pronto empieza a participar en diferentes concursos y certámenes, llegando a cantar a dúo con Josep Carreras en España. En 2002, con solo 15 años, se clasifica en tercera posición en el Festival de música internacional de Bulgaria. Paralelamente prueba suerte en las audiciones de la famosa girl band ucraniana, Via Gra.

Su salto a la fama se produce en 2007 cuando gana la séptima edición de la versión rusa de Operación Triunfo, donde demuestra su versatilidad. Su participación en el concurso no está exenta de la polémica constante que la acompañará a lo largo de su carrera pública, pues es grabada diciéndole a un compañero que «no le gustan las personas chinas ni negras», algo por lo que tiene que pedir perdón. Posteriormente también declara que su único amigo en el programa fue un miembro del equipo de producción. A pesar de los pesares, al final del proyecto sale de gira grupal por Rusia, Ucrania y Estados Unidos. Gracias a su victoria firma un contrato con el famosísimo ucraniano productor Konstantin Meladze y publica sus primeros singles, entre ellos, el dueto Bezotvetno con Valery Meladze con un videoclip dirigido por Alan Badoev.

Y, en 2009, el drama. Anastasia se presenta a la preselección ucraniana para Eurovisión con la canción Za tebe znov, pero en la semifinal, por un malentendido con las reglas del concurso y un vacío legal, canta el tema Vsyo dlya tebya, ya presentado en OT. Eliminada por el jurado por este motivo, la cantante y su manager denuncian a la organización y alegan que las normas no especificaban que en esa gala era obligatorio interpretar la candidatura eurovisiva, sino simplemente realizar una actuación para demostrar sus habilidades artísticas, y cuestionan la integridad de los jueces. La justicia paraliza el proceso de selección, y posteriormente le da la razón a la intérprete, si bien esta llega a un acuerdo con la televisión estatal para que se celebre sin ella la final nacional.

Anastasia, despechada, decide llevar su canción, Mamo, a la preselección rusa, anfitriona de Eurovisión 2009, y para rizar el rizo gana el concurso con el favor tanto del jurado como del televoto. Esta victoria también genera controversia porque los 15 finalistas ya habían sido anunciados por la televisión pública rusa antes de añadir a Prikhodko a la lista. Se suceden los editoriales y las declaraciones cuestionando no solo este hecho, sino también la profesionalidad del jurado y el origen de Anastasia y el idioma bilingüe de Mamo. De hecho, muchos expertos eurovisivos teorizaron a toro pasado sobre el hecho de que una cantante ucraniana representara a Rusia en Moscú 2009 con una canción de temática maternal. En el festival se clasifica en undécima posición con 91 puntos, incluyendo el 12 de Armenia, el 10 de Estonia y los 8 de Bielorrusia, República Checa y Ucrania.

Después de su tumultuosa experiencia eurovisiva, rompe el contrato con Meladze y comienza a trabajar con el productor Igor Goncharenko y su hermano Nazar. En 2011 regresa a la preselección ucraniana con Action que se queda en el puesto 8. En 2012 publica su primer álbum Zazhdalas que recopila sus primeras y nuevas canciones. En 2016 vuelve de nuevo al Vidbir con I Am Free Now que cae en semifinales. Ese mismo año edita su segundo y último disco, Ya vilna. En octubre de 2018 anuncia su retirada de la música para dedicarse exclusivamente a la política.

Esta nueva etapa de su actividad pública comienza en 2014 durante el Euromaidán, la anexión de Crimea y la Guerra del Dombás. En julio de ese año realiza una gira con otros artistas ucranianos para apoyar a las Fuerzas Terrestes de Ucrania, la soberanía nacional y la liberación de la influencia de Rusia. Durante el tour publica en sus redes sociales que los rusos son «estúpidos, de mente estrecha y sordos ante la realidad». Posteriormente acusa a Rusia de ocupar ilegalmente territorio ucraniano y promete no volver a actuar en el país ni cantar en ruso, lo que a la cantante le supone un fuerte impacto económico, pues es su principal mercado musical. En agosto de 2014, el programa 17 amigos de la Junta del canal de televisión ruso NTV dedica una pieza propagandística y difamatoria contra Anastasia tildándola de «rebelde antirrusa», entrevistando a su abuela paterna que la describe como «una vergüenza para la familia» y otra al cantante Joseph Kobzon que criticó su actuación en Eurovisión y la definió como «una chica de la calle que maldice como una prostituta». A finales de 2019 se inscribe en el partido político Patria, liderado por Yulia Tymoshenko y perteneciente a la familia del Partido Popular Europeo. En las elecciones anticipadas de 2019, se presenta en el undécimo distrito electoral de Vinnytsia, pero solo logra el 4,44% de los votos, en octavo lugar, y no obtiene escaño.

Anastasia se casa en 2013 con un excompañero de colegio, Alexander, y tiene dos hijos, Nana, nacida en 2010 fruto de su anterior matrimonio con el empresario abjasio Nurik Kukhilava, y Olexandr, nacido en 2015.