Алексей Шеин мог вызвать особое нерасположение Петра и потому, что до конца оставался в ближайшем окружении царевны Софьи. Когда 29 августа она отправилась в Троице-Сергиев монастырь (куда ушел из Преображенского царь Петр), чтобы в последний раз попробовать договориться с ним, царевну сопровождали ближние бояре В. В. Голицын, В. Д. Долгоруков, М. Я. Черкасский, А. С. Шеин…
Как известно, тогда царевна Софья была отстранена от власти, а потом заключена в Новодевичий монастырь. Ее сторонники подверглись опале.
Однако среди «опальных» не оказалось боярина и воеводы Алексея Семеновича Шеина. В октябре 1689 года он вдруг упоминается в свите царя Петра во время поездки в Преображенское, в ноябре того же года едет с ним в Саввино-Сторожевский монастырь. В 1690 году воевода плывет с царем на судах по Москве-реке в Коломенское. В 1693 году мы видим А. С. Шеина в сравнительно немногочисленной свите Петра во время путешествия в Архангельск, а в 1694 году ему было «указано» во дворце «кормить» патриарха, служившего заупокойную молитву по царице Наталье Кирилловне, матери Петра. Но серьезных государственных и военных поручений Шеин в эти годы не получает. Молодого, но уже прославившегося воеводу как бы держали «в запасе», сохранив за ним почетное место при дворе.
По-иному сложилась судьба боярина и воеводы Бориса Петровича Шереметева. Бурные события государственного переворота не коснулись его. Шереметев оставался в своей прежней должности — воеводой Белгородского «разряда», «ведя войну от курсов обыкновенную» — отбивал на «украине» многочисленные набеги крымских татар. Привычная служба для «пограничного воеводы», беспокойная, но не считавшаяся какой-то особой заслугой. Много было таких воевод на тысячекилометровой степной границе России. Пограничный быт только однажды, в 1692 году, был нарушен приближением большой крымской орды. Воевода Шереметев выступил навстречу с сорокатысячной армией, и татары вернулись обратно в степи.
Изредка Шереметев наезжал в Москву, на свой столичный двор. Во время одного из таких приездов, в мае 1693 года, у него на дворе обедал царь Петр. Это была великая честь. Видимо, всех способных и заслуженных воевод молодой царь держал в поле зрения, потому и посчитал нужным специально показать Борису Шереметеву свое благорасположение.
Действительно, опытные воеводы вскоре понадобились — Петр I готовился к походу на турецкую крепость Азов. Попытки князя Голицына овладеть Перекопом показали все трудности прямого удара по Крымскому ханству. Чтобы непрерывно угрожать хану, необходимо было иметь опорный пункт в непосредственной близости от Крыма, обеспечить свободный выход в Азовское и Черное моря быстрых казачьих флотилий, набегов которых так боялись и крымский хан, и турецкий султан. Обладание Азовом обеспечивало России большие военно-политические преимущества. Закрепившись здесь, можно было думать и о войне за выход к Балтийскому морю…
План похода был утвержден 6 февраля 1695 года военным советом на Пушечном дворе. Он предусматривал нанесение двух ударов: основного — на крепость Азов, вспомогательного — на турецкие крепости в низовьях Днепра, по традиционному маршруту прошлых Крымских походов.
Во главе азовской армии была поставлена «консилия» (военный совет) из трех генералов: А. М. Головина, Ф. Я. Лефорта и П. И. Гордона. Но реальной властью «консилия» не обладала, ее решения вступали в силу только после утверждения «бомбардиром Преображенского полка Петром Алексеевым» (под этим именем находился в армии царь). Таким образом, армия оказалась лишенной единого командования. Молодой и нетерпеливый царь властно вмешивался во все мелочи, сам стрелял из пушек, с киркой и лопатой работал в траншеях под огнем неприятеля, подолгу и шумно пировал со своими любимцами. Горячие и малоопытные советники предлагали непродуманные решения, и царь часто соглашался с ними. Он надеялся, что с Азовом можно справиться легко и быстро, ведь к крепости двигалась отборная, сформированная им самим армия численностью в тридцать одну тысячу человек, в состав которой входили Преображенский, Семеновский, Лефортов и Бутырский полки, многочисленная артиллерия.
Не совсем верные сведения были у русского командования и о гарнизоне Азова, который определили в три тысячи человек. Только возле Черкасска к генералу Гордону, командующему авангардом, был доставлен захваченный казаками некий «Грек», сообщивший, что «в январе месяце был он в Азове по торговым делам: тогда гарнизон состоял из 3000 человек; в марте месяце Муртоза-паша привел 1000 человек; а через неделю пришли из Кафы четыре корабля с 2000; из Константинополя ждут еще 3 корабля и 10 фуркат с войском, снарядами и продовольствием. С самого начала весны турки укрепляли Азов: вычистили рвы, одели каменную стену дерном, поставили батареи; главнокомандующим в городе Муртоза-паша, по нем Мустафа-бей».
Стало очевидно, что неожиданного нападения не получилось, турки основательно подготовились к обороне. Кроме того, под Азовом собирались значительные силы крымской конницы. Донской атаман Фрол Минаев настоятельно советовал не приближаться к Азову до прибытия главных сил русской армии, тем более что под Азовом стояла еще и сильная турецкая эскадра. На военном совете многие офицеры придерживались того же мнения, но генерал Гордон имел строгий приказ царя…