Анна была сразу же зачислена в корифейки Мариинского театра, минуя кордебалет. Она только начинала свое стремительное восхождение к вершине, где в это время царствовали М. Кшесинская, О. Преображенская, Ю. Седова, В. Трефилова, Л. Егорова, А. Ваганова. Они получали сольные партии. Павловой почти в каждом спектакле поручали один-два танца, и она умела их превратить в небольшую роль, удивляя публику не столько виртуозностью исполнения, сколько потоком чувств, заставляющих зал дышать с ней в унисон.
Даже облик Павловой отличался от «идеальных», довольно пышных в те годы стандартов – она была маленькая, с утонченными пропорциями тела. Линия шеи плавно спускалась к тонким плечикам, нервные изящные руки и прелестные ножки с тонкими щиколотками и круто выгнутым подъемом – ноги «богини танца». Шаг ее был невесом, казалось, балетные туфельки не прикасаются к полу, а скользят, летят. В каждом танце были одни и те же балетные «па», но Павлова никогда не повторялась.
«Новенькую» почти сразу отметил знаменитый в прошлом солист балета Его Величества, а теперь – балетмейстер, Мариус Петипа. Он выделил ее даже в ущерб своей дочери Любе, отдав партию Флоры («Пробуждение Флоры») Павловой. Ах, какой замечательной парой в этом балете они были с Михаилом Фокиным! Безгранично талантливые и такие разные. Анна органично вписывалась в фантастический, но застывший мир классического балета. А Фокин все чего-то искал, куда-то стремился. Академические спектакли заставляли будущего знаменитого балетмейстера кривиться, словно от запаха нафталина. Но оба уверенно шли к вершинам.
В архиве дирекции императорских театров дело Павловой хранилось под № 2335. 1899 г. – зачислена в Мариинский театр; 1902 г. – переведена из корифеек во вторые танцовщицы; 1903 г. – училась в Милане у знаменитой в прошлом танцовщицы Беретты, должность первой танцовщицы; 1906 г. – «переведена в разряд балерин с окладом в 3000 рублей в год». Скупые строки чиновников, а между ними десятки ролей – от номеров балетного дивертисмента до сольных партий. Молодая балерина выносила на своих плечах обширнейший репертуар: Жизель и принцесса Аврора, Никия и Раймонда, Ундина, Китри, Пахита. «Павлова была феноменом, и ее энергия была неистощимой энергией гения», – писал У. Хайден, пианист, а впоследствии дирижер ее труппы.
Жизнь стремительно пролетала мимо Анны. Многочисленные поклонники, зачастившие в ее театральную уборную и дом, не заставляли замирать сердце балерины от предчувствия человеческого счастья. Иногда она с завистью поглядывала на других танцовщиц, заводивших многочисленные любовные интрижки. Личной жизнью Павловой оставался танец, пока в ее окружении не появился Виктор Эмильевич Дандре. Отпрыск аристократического рода с французскими корнями числился в «списках сливок» петербургской золотой молодежи: богат, хорош собой, имел чин придворного советника и в сенатском департаменте занимал не последнее место. Ему по «чину» положено было иметь «малютку из балета». Виктор слыл заядлым балетоманом и Павлову выделил сразу: воздушное хрупкое создание, обладающее чарующей выразительностью каждого жеста. Анну стали часто замечать в его роскошной квартире. Она мучилась положением содержанки и мечтала стать «мадам Дандре».
Жениться на танцовщице Виктор не собирался. Он говорил, что нужно думать о ее карьере, а она мечтала о семье. Любовь, вспыхнувшая между ними, стала единственной и в ее, и в его жизни, но была полна боли и надрыва, каждый из них побывал в роли и тирана, и жертвы. В 1906 г. Виктор купил на имя Анны прекрасный дом, и «Петербургская газета» тут же сообщила своим читателям: «Наши балетные артистки позволяют себе роскошь, которой не знали прежние балерины: г-жа Павлова 2-я устраивает у себя на квартире танцевальный зал со всеми приспособлениями для практических занятий». Теперь она могла репетировать даже дома.
Конец 1905 – начало 1906 г. стали цепью сплошных триумфов для Павловой: «Дон Кихот», «Очарованный лес», «Дочь фараона», гастроли в Москве. Она не просто достигла уровня признанных балерин Мариинки, но сумела превзойти их, придавая «допотопным композициям» классического танца утонченность, очарование и неземную грацию.
Новую живую струю в репертуар Павловой внесла работа с Фокиным как с балетмейстером («Виноградная лоза», «Евника», «Шопениана», «Египетские ночи», «Павильон Артемиды», «Сильфида» и др.). Но вершиной сотрудничества двух гениев балета стала созданная за несколько часов под звуки мандолины (Фокин учился играть на этом инструменте) и завывание декабрьской вьюги легендарная хореографическая миниатюра «Лебедь» (1907 г.).