Первый удар в очередной раз был нанесен по Азову, принадлежавшему Турции и запиравшему выход к Черному морю. Кроме того, России необходим был опорный пункт вблизи Крыма для дальнейших походов. Весной 1695 года часть армии, под командованием Бориса Шереметева по Днепру пошла к Крыму, а тридцатитысячное войско с царем Петром I реками спустилась до Царицина, прошло к Дону и в июне было под Азовом. После трехмесячной неудачной осады Азова, основной причиной которой было отсутствие у русских флота, вследствие чего было невозможно осуществить блокаду крепости, русское войско в октябре 1695 года ушло от Азова. Отвлекающий поход русской армии под командой Бориса Петровича Шереметева был более удачен. В июне 1695 года русское войско осадило и 30 июля, взорвав подземную мину у стены крепости, взяло турецкую крепость на Днепре Кызыкермен, отбившись от крымско-татарской конницы Ширин– бея. После этого захватив и разрушив турецкие крепости на Днепре Мустриткермен, Исламкермен, Мубареккермен и построив на одном из днепровских островов крепость, названную Таваном, Шереметев вернулся в Белгород.
В отместку за потерю крепостей крымский хан в феврале 1696 года совершил набег на полтавские земли Украины, но войска Шереметева и казаки украинского гетмана Ивана Мазепы отразили нападение.
Построив на новых верфях на реке Воронеж к апрелю 1696 года 2 корабля, 4 брандера, 23 галеры и 1300 стругов для перевозки войск, Петру I с сорокатысячной армией, отрядами донских и запорожских казаков, удалось уничтожить турецкие корабли, прикрывавшие Азов, вывести русские суда в море и полностью окружить Азов. 19 июня 1696 года турецкий гарнизон в Азове капитулировал. Уходя из крепости турки оставили русским 16 знамен и 136 пушек.
Осенью 1696 года Петром I и Боярской Думой было принято решение начать освоение новых земель. Первенцем оказался город Таганрог, отстроенный в том же году, там же была оборудована гавань для российского флота в Азовском море. В 1697 году тридцатитысячное русское войско во главе с Алексеем Семеновичем Шеиным вошло в Приазовье. Русские укрепили Азов, отбив нападение двадцатитысячного татарского отряда, продолжавшегося десять часов, построили против города на северной стороне Дона новую крепость, сделали гавань в Таганроге, построили для защиты города крепость Троицы и форт Павловский на Петрушинской косе. Приазовье закреплялось за Россией.
Вторая русская армия, сформированная в Белгороде князем Я.Ф.Долгоруким с целью отвлечь войска крымских татар от армии Шеина, тогда же прошла вдоль Днепра и опять взяла восстановленную турками крепость Кызыкермен и Таван, оставив там гарнизоны. Крепости были атакованы турецкой армией белгород– днестровского паши Али и крымско-татарской конницей с ханом Эльхадж-Селим Гиреем во главе. Русский гарнизон Тавана с воеводой, думным дворянином Бухвостовым, отбил все приступы. После того, как в крепость прорвались с боем пришедшие на помощь запорожские казаки кошевого Григория Яковенко, турки с татарами дважды, ожесточенно, но неудачно штурмовали Таван. При приближении большого отряда полтавского полковника Искры они ушли в Очаков.
До нашего времени сохранились письма крымских татар к осажденным и их ответ: Татарское письмо, пушенное в Таван на стреле 23 сентября 1697 года:
«В сем городе находящимся сотникам черкасским и казакам поздравление! Мы с вами исстари друзья; для чего же сражаетесь за сей наш город и умираете за Москву, вам недоброжелательную? Оставьте лучше сопротивление и сдайте защищаемую вами крепость. Если вы согласны на сие предложение, пришлите одного из ваших товарищей к желтому знамени. Мы ханскому величеству донесем и все станется, даст Бог, по вашему желанию; в противном случае делайте, что хотите, греши ваши на ваших шеях.»
Татарское письмо, пущенное в Таван на стреле 24 сентября 1697 года»:
«От всего турецкого войска и хана крымского слово: да будет ведомо вам, таванской старшине и войску московскому и казацкому, что всеми землями обладает великий наш повелитель, султан турецкий, и что защищаемый вами город ему принадлежит. Итак, если желаете сохранить свое здоровье и свободу, возвратите нам оный без всякого повреждения; иначе, с помощью Единого Бога и Магомета пророка, возьмем мы сей город и вас всех вырубим своими кавалерами. Однажды и дважды вам говорим: сдайте город.»
Ответ осажденных, пущенный на стреле в татарский стан: