Постановили — двинуть войска на юг. У Петра нашлись умные советники, план составили блестящий. Ведь противник привык, что Голицын водил армии на Крым, а с Дона проводились отвлекающие операции. Теперь задумали наоборот. Большая армия Шереметева пойдет, как и раньше, вдоль Днепра. Отвлечет татар и турок на себя. А вторая армия будет маленькой, зато отборной. 31 тыс. бойцов — Преображенский, Семеновский полки, старая гвардия — Бутырский и Лефортовский полки. А также московские стрельцы, солдаты Тамбовского разряда, казаки. Азов имел три линии мощных укреплений — земляной вал со рвом и палисадом, каменную стену с 11 башнями, внутренний замок. Крепость защищали более 100 орудий, выше по Дону турки построили две каланчи, перекрывшие реку цепями и артиллерией. Но гарнизон был небольшим, 3 тыс. человек, и расчет строился на внезапности — налететь, штурмовать, и десятикратное превосходство гарантирует победу.
Однако расчеты перечеркнулись грубейшими ошибками. Вместо одного командующего Петр назначил «консилию» из Лефорта, Головина и Гордона. Она должна была выносить совместные решения, а утверждал их царь. Хотя военный опыт Лефорта ограничивался уровнем младшего офицера, а у Головина такового не было вообще. Чтобы двигаться побыстрее и ударить неожиданно, решили не брать тяжелых орудий, только легкие. Но при этом о планах болтали на всех застольях, а шпионов в Москве хватало. Турки узнали, как намерен действовать царь. Успели изготовиться, увеличили гарнизон до 10 тыс.
Авангарды царской армии подошли к крепости в конце июня 1695 г. Но и турки продолжали подвозить морем подкрепления, к крепости проскочили еще 20 галер с янычарами. Из степи нападала татарская конница, не пропускала обозы с припасами. А осада началась бестолково. Легкие орудия не причиняли стенам вреда. Царь повсюду лез, как мальчишка. Сам палил из пушек, с лопатой копал траншеи, а по вечерам в его шатрах шумно пировали. Генерал Патрик Гордон писал: «Судя по нашим действиям, иногда казалось, будто мы затеяли все это не всерьез». Успеха добились только донские казаки. Дерзкой ночной атакой они захватили каланчи на реке, взяли 21 орудие. Но их победу тут же омрачило поражение. К туркам перебежал голландец Янсен, подсказал, что на стыке корпусов Лефорта и Гордона не завершены полевые укрепления. Защитники внезапно выплеснулись контратакой на этот участок, перебили 600 солдат.
Шереметев действовал куда более грамотно. Его армия спустилась вдоль Днепра, соединилась с полками украинских казаков, которых привел Мазепа. Подступили к крепости Кызы-Кермен. Она была послабее Азова, но тоже крепким орешком — каменные стены, 30 орудий. Поблизости держались татары ханского сына Нуреддина. Но Шереметев выслал против крымцев заслоны кавалерии, а крепость велел окружать шанцами, ставить батареи. Вылазки янычар отразили, открыли бомбардировку. Быстро вырыли минные подкопы. 30 июля взрыв мины пробил огромную брешь в стене. Комендант крепости Амир-паша, понял, что дальнейшее сопротивление бесполезно, и капитулировал. У русских обошлось почти без потерь, «полону взяли множество, также и пожитков. А стояли под ним пять дней, в шестой взяли». В других турецких крепостях поднялась паника. Гарнизоны Аслан-Кермена и Тавана сбежали, их заняли без боя.
Петру до таких успехов было далеко. Он назначил штурм. Гордон возражал, что без проломов в стенах, без достаточного количества фашин и лестниц атаковать бессмысленно, но его доводы отмели. 5 августа солдаты пошли на приступ. Бутырский и Тамбовский полки все-таки прорвались к городским укреплениям, вскарабкались на угловой бастион и захватили его. Но дивизия Головина задержалась в садах, опоздала с атакой. Турки сняли с ее участка подкрепления, перебросили к месту прорыва и вышибли русских. Неудачный штурм обошелся в 1500 убитых.
Лишь после этого решили брать Азов осадой, подводить мины. Но турки мешали, не прекращали вылазок. Минные подкопы они обнаружили и взорвали. Петр велел рыть новые. Завершили их только 20 сентября, штурм назначили на 25-е. Из двух мин сработала одна. В пролом ворвался Лефортовский полк, неприятели его выбили контратакой. А ночью ударили… заморозки. 27-го «консилия» постановила отступать. Пока собирали имущество, сворачивали лагерь, выступили лишь 2 октября. Побрели по степям, под дождями. 18 октября «был великий снег». Но войска-то были в летнем обмундировании. Тысячи солдат замерзли, пообморозились, другие брели больными, кутались не пойми во что.