27 мая 1696 года русский флот вышел в море, отбросил турецкие суда и в начале июня блокировал Азов. Одновременно к Азову подошли главные силы русской армии. Теперь крепость была блокирована со всех сторон.
Штурму Азова предшествовал яркий эпизод — поединок сильнейших представителей противников. Прямо как в рыцарские времена. Турецкий комендант крепости Азов Хасан-Арслан предложил провести кинжальный бой двух богатырей, и назначил опытного бойца из черкесов. Петр I со своей стороны выставил известного ему широкоплечего, сильного и храброго участника Крымских и Азовских походов башкира из Бурзянской волости Алдар-батыра Исекеева. Вскоре на площадке перед крепостью гонг известил о начале поединка. Летописец похода отмечал большую физическую силу обоих бойцов: «…окропилась земля, как утренняя роса, кровью каждого — сына башкирского и сына черкесского; пали они на землю, подымая клубы пыли, крепко лупцевали друг друга». Алдар-батыр вышел победителем из этой схватки.
Первый штурм не удался: помешала атака крымских татар — союзников турок с правого берега Днепра. По указанию А. С. Шеина донские и башкирские казаки отбили эту атаку, но время было упущено. А во время контратаки против крымских татар получил легкое ранение и Алдар-батыр.
Генералиссимус Шеин стал готовить второй штурм Азова. В тыл противника он послал разведку — Алдар-батыра и Бирдикуля. «Нужен язык, — сказал генералиссимус. — Что хотите делайте, но добудьте пленного». Разведчики сумели проникнуть в тыл врага и захватили в плен знатного бека. Но были замечены турками, которые ринулись в погоню. Настигнутые в поле разведчики оказали серьезное сопротивление, но лишь четверым, в том числе и раненому Алдар-батыру удалось вернуться в лагерь русских войск. И генералиссимус, и сам царь Петр I высоко оценили подвиг разведчиков, все они получили царские грамоты. Грамота Алдар-батыра гласила: «Тархану Алдарбею Исекееву — детям его, племянникам и внучатам — за бытие им, Алдаром, в Крымском и Азовском походах и за три полученные им раны, также и за убийство сразившегося с ним Черкешенина, за поимку языка Крымчанина… и объявление Его Величеству блажения и вечной славы достойная память Государю Императору Первому».
Победа Алдар-батыра в поединке перед началом первого штурма как-то предопределила и победу всего русского войска. 18 июля 1696 года совместными действиями армии и флота был взят и Азов. Москва торжественно встречала победителей. Генералиссимус А. С. Шеин въехал в столицу на белом коне в сопровождении 30 всадников, а Петр I шел в пешем строю в немецкой одежде. Второй генералиссимус и князь-кесарь Ф. Ромодановский присвоил царю Петру за эту победу звание капитана.
