Встретив его на балу, она захотела отличить знаменитого поэта и выбрала его в одном из танцев; опасение, что он посмеется над ней, заставило ее, подходя, опустить глаза и покраснеть. Ее задела небрежность, с которой он спросил, где ее место. Ее задела мысль, что Пушкин может принять ее за дурочку, но она ответила просто и уже весь вечер не пыталась его выбирать. Тогда он, в свою очередь, подошел и пригласил ее на фигуру. Она подала ему руку и, чуть отвернувшись, улыбнулась. Ведь такой чести все добивались». После этого романтического знакомства проницательная девушка отметила некоторые сексуальные особенности поэта.
«Среди особенностей поэта была та, что он питал страсть к маленьким ножкам, о которых он в одной из своих поэм признавался, что предпочитает их даже красоте. Анета соединяла с непосредственной внешностью две вещи: у нее были глаза, которые порой бывали хороши, порой глупы, Но ее нога была действительно очень мала, и почти никто из ее подруг не мог надеть ее туфель. Пушкин заметил это преимущество, и его жадные глаза следили по блестящему паркету за ножками молодой Олениной».
После первой встречи поэт стал часто бывать в их доме и на даче в Приютине. Постепенно Пушкин увлекся юной красавицей чуть более серьезно. А в ответ на хвалебную оду Вяземского по поводу прекрасных глаз Александры Россет Пушкин написал очень милые стихи, посвященные своему новому увлечению:
Весною 1828 года Пушкин почти ежедневно встречается с нею в Летнем Саду, куда ходил гулять с Вяземским и Плетневым. «Девица Оленина, – писал Вяземский жене, – довольно бойкая штучка. Пушкин называет ее «драгунчиком» и за этим «драгунчиком» ухаживает. Чрезвычайно подвижная, бойкая, светская, с поразительно миниатюрными ножками и прелестными глазами Анна Оленина казалась поэту той самой девушкой, которая могла бы составить «счастье его жизни», стать ему верной подругой, женою. В рукописях Пушкина появляются записи: Eninelo, Etenna Eninelo – ее имя и фамилия, прочитанные с конца. Он окружает начертание милого имени виньеткой. Annette Olenine, пишет он и заменяет ее фамилию своей: Annette Pouchkine. Запись эта выдает его мечту…
Поэт посвящает ей много стихов, однажды Оленина нечаянно сказала Пушкину «ты». В следующее свое посещение поэт привез ей стихи:
В другом стихотворении («Зачем твой дивный карандаш…») он призывает знаменитого английского художника Доу запечатлеть вместо своего «арапского профиля» – «ее черты» – олицетворение «юности и красоты»
В первых числах июня 1828 года Пушкин услышал у Олениных привезенную с Кавказа А. С. Грибоедовым и обработанную М. И. Глинкой грузинскую мелодию. Анна Алексеевна, как показалось Пушкину, прекрасно пела ее. Тогда, 12 июня, было создано изумительное стихотворение «Не пой, красавица, при мне», записанное в альбом Анны Алексеевны: