Не будем гадать, личность проявляется через деяния, а об этом свидетельства современников, пусть и скупые, сохранились…

Для Алексея Шеина, как и для Бориса Шереметева, первой большой войной стали Крымские походы. В дальнейшем их судьбы, причудливо переплетаясь, пройдут через все военные события последнего десятилетия XVII в.

О предстоящем походе было объявлено в сентябре 1686 г. Всем «ратным людям» приказано готовиться и ждать указа о выступлении на сборные пункты. В октябре прошло назначение воевод в полки. Главнокомандующим стал князь Голицын с громким титулом «Большого полка дворового воеводы, царственные большие и государственных великих дел сберегателя и наместника Новгородского». В «товарищах» у него оказались воеводы А.С. Шеин, князь В.Д. Долгоруков и окольничий Л.Р. Неплюев. «Ратные люди» получили приказ собираться в полки в Ахтырке, Сумах, Хотмышске, Красном Куге. Посланы были грамоты на Дон и в Запорожскую Сечь: казачьи полки должны были действовать на флангах.

Русская армия состояла из большого полка и четырех разрядных: Севского, Низового (Казанского), Новгородского и Рязанского.

Новгородским разрядным полком, состоявшим из нескольких солдатских, драгунских, рейтарских и стрелецких полков, а также сотенной дворянской конницы, командовали боярин и воевода А.С. Шеин и князь Д.А. Барятинский.

Первый Крымский поход был неудачным, русская армия даже не дошла до Перекопа, хотя ее численность была значительной (до 100 тыс. человек). Имена Алексея Шеина и Бориса Шереметева в «разрядах» этого похода не упоминались: видимо, воеводы еще не играли самостоятельной роли. По-иному было во время Второго Крымского похода (1689 г.).

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

Авангард Алексея Шеина неоднократно отбивал «наезды» многочисленной крымской конницы, умело и отважно сражался с крымцами и Борис Шереметев.

Второй Крымский поход тоже закончился неудачей, однако царевна Софья пыталась представить его победоносным, воеводы были встречены в Москве с великой честью, розданы щедрые награды и пожалования. По-иному встретил их молодой царь Петр Алексеевич, он даже отказал в приеме В.В. Голицыну, А.С. Шеину и другим «большим» воеводам. Алексей Шеин мог вызвать особое нерасположение Петра, потому что до конца оставался в ближайшем окружении царевны Софьи. Когда 29 августа она отправилась в Троице-Сергиев монастырь (куда ушел из Преображенского царь Петр), чтобы в последний раз попробовать договориться с ним, царевну сопровождали ближние бояре В.В. Голицын, В.Д. Долгоруков, М.Я. Черкасский, А.С. Шеин…