Репертуар Большого (Каменного) театра привлекал в театр молодых вольнодумцев, среди которых был и юный Пушкин. Молодой поэт высоко ценил искусство Истоминой. В течение некоторого времени Пушкин даже считал себя влюбленным в Истомину – как он сам писал, «когда-то волочился» за нею.

Среди друзей Истоминой был и Александр Грибоедов. Судя по всему, отношения были очень доверительные – поссорившись с любовником, пожаловалась она именно Грибоедову.

Юная Истомина предпочла множеству воздыхателей кавалергарда Василия Шереметева – веселого, добродушного, слегка ветреного, но при этом ревнивого. Она сблизилась с ним и поселилась на его квартире, где прожила около двух лет. Как-то после очередного выяснения отношений она решила на время поселиться у подруги. Грибоедов, провожая поздно вечером огорченную Истомину после спектакля, пригласил ее к себе на чашку чая. Он жил в это время на квартире у приятеля – камер-юнкера Александра Завадовского, некогда ухаживавшего за танцовщицей. Завадовский и Истомина встретились – а что между ними вышло, уже никто никогда не узнает. То ли она провела в обществе Завадовского двое суток, то ли не провела… Но потом она уехала на квартиру к подруге, где ее и разыскал Шереметев. Состоялось неприятное объяснение, и Истомина явно наговорила своему избраннику лишнего. Шереметев, возмутившись, вызвал на дуэль Завадовского, а поскольку в эту историю был замешан Грибоедов, то он получил вызов от друга Шереметева, Якубовича.

Двойной поединок, вошедший в историю как «дуэль четверых», состоялся на Волковом кладбище. Первыми стрелялись Завадовский и Шереметев. Шереметев был тяжело ранен, и Якубович с Грибоедовым решили отложить дуэль, потому что кавалергарда следовало доставить домой. Шереметев скончался через сутки, а Грибоедов и Якубович стрелялись уже на Кавказе. Пуля Якубовича повредила руку драматургу, и именно по изуродованному пальцу опознали его тело после тегеранской резни в январе 1829 года.

Танцовщица долго оплакивала убитого возлюбленного. Но жизнь продолжалась, Дидло ставил все новые спектакли.

В балетах на мифологические сюжеты она была великолепна. Кроме блестящей хореографии она обладала способностью перевоплощения, находя новые и яркие краски для каждого создаваемого ею сценического образа. Публика любила ее еще и за то, что она никогда не повторялась в своей игре, не пользовалась заученными штампами, каждую партию исполняя по-разному, находя присущие лишь этому образу оттенки движений и мимической игры. Обладала Истомина и немалым комедийным даром, или, как писала критика тех лет, она не только «танцует с величайшей живостью и проворством, она отличная балетная актриса для ролей резвых и хитрых девиц».

15 января 1823 года состоялась премьера балета «Кавказский пленник, или Тень невесты» по мотивам пушкинской поэмы. Истомина стала первой исполнительницей роли Черкешенки. Пушкин, узнав о спектакле, писал брату в Санкт-Петербург из Кишинева: «Пиши мне о Дидло, о Черкешенке Истоминой, за которой я когда-то волочился, подобно Кавказскому пленнику».

В репертуаре Авдотьи Истоминой комические роли чередовались с драматическими, лирическими и трагедийными. Героический характер Истомина воплощала на сцене с не меньшим мастерством. Бурный восторг публики вызвало ее выступление в роли Луизы в пантомимном балете «Деревенская героиня», где Истомина играла женщину поистине героического характера, честную и бесстрашную. Таков же характер ее героини и в балете «Дезертир».

Способность Истоминой к перевоплощению была поистине великолепной. Она сумела с точностью передать манеру поведения и мимики восточной девушки в сказочном балете «Калиф багдадский». А после премьеры «Кавказского пленника» по Петербургу распространились даже слухи, что Истомина действительно черкешенка по происхождению.