Круг поклонников Павловой постоянно расширялся. Многие пытались, как это тогда было принято, взять покровительство над юной танцовщицей. Хоть Анна и не вполне соответствовала тогдашним канонам красоты, она все же была на редкость хороша: обаятельная, изысканная, с царственным лицом. Особенно украшали ее улыбка и глубокие темные глаза. Но Павлова отметала все предложения – вежливо, очень тактично, но твердо. Потом среди прочих она стала выделять одного: Виктора Дандре.
Виктор Эмильевич Дандре, потомок знатного рода, знаток балета, удачливый предприниматель, обер-прокурор Сената, стал первым, главным и единственным мужчиной в жизни Анны Павловой. Некрасивый, на 11 лет старше ее, поначалу он стал Павловой другом и советчиком в делах балета, а затем сумел добиться ее любви. Он возил ее по ресторанам, делал подарки, самым крупным из которых был дом на Английском проспекте, где был сделан огромный репетиционный зал с белыми стенами и портретом Тальони. Влюбленная Павлова верила Дандре во всем, но, когда поняла, что он значит для нее гораздо больше, чем она для него, и никакого будущего у них нет, отошла в сторону. Отныне ее единственной любовью и страстью стал балет.
Она неуклонно шлифовала свое мастерство. Еще в 1903 году ездила в Италию в студию к знаменитой Катарине Беретта, занималась у Мариуса Петипа – главного балетмейстера Мариинки. С первых лет работы в театре Павлова начала танцевать с Михаилом Фокиным, который окончил училище на несколько лет раньше и уже стал известен как прекрасный танцовщик. Фокин стремился и к деятельности постановщика, реформатора балетных форм. Сильное влияние на него оказали идеи Айседоры Дункан, которая приезжала в Петербург на гастроли. Дуэт Павловой и Фокина быстро перерос в творческий союз. Фокин нашел в Анне идеальную исполнительницу своих замыслов: ее разностороннее дарование и умение воплотить на сцене любой образ Фокин знал и ценил. Их взгляды на искусство во многом совпадали: они оба считали, что пришло время обновить русский балет, сохранив при этом его лучшие традиции, привнести в условное балетное искусство приемы, приближающие его к настоящей жизни. Оба стремились к единству всех элементов балетного спектакля: музыки, хореографии, костюмов и декораций, чего на балетной сцене давно уже не было и в помине.
Павлова участвовала практически во всех первых новаторских постановках Фокина. В 1906 году Павлова танцует в его «Виноградной лозе» Рубинштейна, на следующий год – в «Эвнике». В этом балете, стилизованном под античные изображения, танцовщики выступали в хитонах, босые, на полупальцах. Поначалу Павловой досталась роль Актеи, а заглавную партию танцевала официальная прима Мариинки Матильда Кшесинская. Но вскоре Кшесинская от этой мало подходящей ей роли отказалась, и Эвнику стала танцевать Павлова.
В балете «Египетские ночи», поставленном по мотивам египетских фресок, Павлова исполняла роль египтянки Вереники, затем была главная партия в «Павильоне Армиды», возрождающем стиль барочной Франции. Специально для Павловой Фокиным была поставлена знаменитая «Шопениана» (она же «Сильфиды»). Тогда же был создан номер, ставший этапным не только для Павловой, но и для всего мирового балета: прославленный «Лебедь» на музыку Сен-Санса.
История его создания очень проста. В декабре 1907 года Павловой понадобился номер для выступления на благотворительном концерте в Дворянском собрании, и она обратилась к Фокину. Тот в это время учился играть на мандолине и как раз разучивал мелодию Сен-Санса. Он предложил Павловой сделать номер на эту музыку. Миниатюру сочинили буквально за несколько минут: сначала Фокин показал Павловой несколько движений, она тут же повторила их, что-то добавила, что-то изменила… Гениальный в своей простоте номер стал на долгие годы визитной карточкой Анны Павловой. Он постоянно развивался: свет сменился с резкого концертного на «лунный», изменилось внутреннее содержание танца, затем номер стал называться «Умирающий лебедь», но сила его воздействия на зрителя со временем не ослабевала. Его исполняли и до сих пор исполняют многие балерины.
В 1913 году Сен-Санс посетил Павлову в ее лондонском доме. Он играл для нее, она для него танцевала. «Никогда мне уже не сочинить ничего, достойного стать наравне с вашим «Лебедем», – сказал он ей.