Анастасия Волочкова родилась в Ленинграде (Санкт-Петербурге) в 1976 году. Ее призвание определилось в раннем детстве и привело в Санкт-Петербургскую Академию русского балета имени А.Я. Вагановой. Она обратила на себя внимание Наталии Михайловны Дудинской, выдающейся русской балерины и педагога. Будучи ученицей ее класса, Анастасия Волочкова удачно дебютировала на сценах Мариинского и Большого театров. На последнем курсе Академии она стала стажером Мариинского театра и исполнила партии Повелительницы дриад («Дон Кихот») и Одетты-Одиллии («Лебединое озеро»).
Успешный дебют в «Лебедином озере» и одновременно выпускной экзамен принес диплом с отличием и в 1994 году открыл молодой солистке двери Мариинского театра в Санкт-Петербурге.
В 1998 году следует приглашение в Большой театр России. В марте этого года Анастасия Волочкова дебютирует здесь в партии Царевны-Лебедь («Лебединое озеро», постановка Владимира Васильева). За этой ролью выстраивается ряд других ведущих партий.
Весной 2000 года Анастасия Волочкова принимает участие в балетном конкурсе в Сен-Пельтене (Австрия) и становится обладательницей приза «Золотой лев» – «самой талантливой балерине Европы». В 2000 году она вынуждена покинуть Большой театр.
В 2001 году по требованию хореографа Юрия Григоровича к дирекции Большого театра Анастасия Волочкова вновь приглашается на эту сцену, чтобы участвовать в постановке балета «Лебединое озеро». Возвращение балерины в Большой и исполнение партии Одетты-Одиллии в марте 2001 года имеет беспрецедентный резонанс в критике и прессе.