И снова в путь — через Австрию, Польшу, где по-прежнему не было ни «приставов», ни подвод, ни корма. Три месяца длилось изнурительное путешествие. Только 27 июля Шереметев представил в Москве доклад о посольстве. В это время князь Василий Голицын находился уже в походе. Может быть, поэтому и награда за посольские труды последовала только в ноябре. Борис Шереметев получил серебряный кубок в три фунта весом, два «сорока» соболей, золотой атлас в пятьдесят рублей и сто рублей денег. Отдельно за хлопоты о «титуле» ему было пожаловано две тысячи «ефимков» — так высоко оценено старание поддержать честь России!
А в декабре 1687 года боярин и воевода Борис Шереметев был назначен главой Белгородского «разряда», командующим войсками, собранными для обороны южной границы. 17 декабря он выехал в город Севск, поближе к своим полкам. Первый Крымский поход обошелся без него, но готовить новый поход предстояло воеводе Шереметеву…
Алексей Семенович Шеин, правнук героя Смоленской обороны, был на десять лет моложе — он родился в 1662 году. Мальчика очень рано «взяли ко двору», и с 1672 года его имя постоянно упоминается в разрядных книгах при описании различных придворных церемоний: он «наряжал вина», «смотрел в государев стол» при торжественных обедах, стоял рындой на приемах иноземных послов, сопровождал царя в «походах» по пригородным селам и монастырям. В этом нет ничего удивительного: Шеины принадлежали к одному из шестнадцати знатнейших родов России, представители которых имели право получать боярские чины, минуя обычную ступень окольничего. В 1680 году Алексей Шеин упоминается уже среди «комнатных стольников». Это была вершина юношеской придворной службы, после которой они отправлялись «в полки», или, как исключение, воеводами в маленькие города.
Алексей Шеин стал таким исключением. В 1680 году он получил назначение воеводой в Тобольск. Пожалуй, лучшую жизненную школу трудно было найти. За тысячи верст от Москвы, от въедливой опеки приказных дьяков, тобольский воевода являлся полновластным правителем огромного края. Помощи и подсказки ждать не от кого, надеяться можно только на себя. Шеин пробыл воеводой в Тобольске почти два года.
Вернувшись в Москву в начале 1682 года, он сразу занимает почетное место в государственной и придворной жизни. 12 января вместе с другими придворными «чинами» подписывает соборный приговор об отмене местничества. Весной поднимается на ступень, которой достигали очень немногие, — получает чин боярина. В «Разряде без мест царя и великого князя Федора Алексеевича всеа Великия и Малыя и белыя Руси» сохранилась запись: «Того же году (1682 года) апреля в 10 день пожаловал велики государь в бояре стольника и ближнего человека Алексея Семеновича Шеина. А сказывал ему боярство думный дьяк Василей Семенов; у скаски стоял и великому государю объявлял околничей Иван Федорович Волинский».
Через семнадцать дней умер царь Федор Алексеевич, но Алексей Семенович Шеин остался «ближним человеком» и при новых правителях. В коронационных торжествах он занимает видное место. Как записано в «Книге записной царства царей государей и великих князей Ивана Алексеевича, Петра Алексеевича», 25 июня 1682 года «изволили великие государи итти из своих государских хором в Грановитую палату, а перед ними шли околничеи и ближние люди, а за ними великими государи шли царевичи и бояре и думные люди, а были в золотых кафтанах. Шапки несли бояре: Алексей Семенович Шеин, князь Иван Борисович Троекуров. А как венчали государей в Соборе, указали держать шапки боярам на золотых мисах: Алексею Семеновичу Шеину Да князю Ивану Борисовичу Троекурову».
Великая честь — стоять рядом с государями во время венчания на царство, блестящие перспективы придворной карьеры сулила эта близость. Но Алексей Семенович Шеин был прежде всего воеводой, и именно так на него смотрели «сильные мира сего». И еще оценивали как верного человека, которому можно поручить самое ответственное и щекотливое дело. Осенью 1682 года, когда царевна Софья покинула Москву, оказавшуюся во власти восставших стрельцов, и начала собирать дворянское ополчение, воевода Шеин был послан в Коломну — собрать и возглавить коломенских, рязанских, тульских и каширских дворян и «детей боярских». В 1683 году Шеин поехал воеводой в Курск, и не с обычным «наказом» Ему предстояло «устроить слободами» на южном рубеже несколько стрелецких полков, высланных из Москвы. В таком деле мало быть только воеводой, требовались и способности политика, потому что стрельцы, крайне недовольные отправкой из столицы, еще помнили те времена, когда они диктовали свою волю боярам и даже самой царевне Софье. Алексей Шеин выполнил это поручение и возвратился в Москву.