Когда война на Украине с Дорошенкой и турками требовала всё новой и новой силы, то по всей стране велено было забрать в ратные люди всё, что было молодого и сильного, и Алексей должен был поступить на службу. Никита Петрович поехал сам проводить сына в Москву и отдать его под покровительство знакомым и сильным людям, пользовавшимся милостями самого царя. В Москве просил он за сына у боярина Артамона Сергеевича Матвеева, приближённого ко двору. Молодой Стародубский хотя и прожил детство и годы юности в глухой вотчине отца, но был смышлёнее многих боярских сынков, проживавших в Москве, в виду у царя, или служивших в ратных людях. Он был смышлёнее, вдумчивее их и с особым уважением относился к более развитым людям; особенно интересовало его всё, что он видел и слышал в доме боярина Матвеева, который радушно принял его отца и ласково обратил внимание на Алексея. К нему ласково относились и все бояре, знавшие давно его отца; молодость, красивое лицо и разумная, сдержанная речь располагали в его пользу. Кроме того, он ехал в дальний поход и ни у кого не стоял на дороге к местам и чинам в самой Москве; не намерен был остаться всем бельмом на глазу своим статным видом и старинным родом. Несколько месяцев, однако, пробыл в Москве молодой Стародубский, прежде чем сформированы были новые полки и нашлись деньги для отправки их в поход. В эту бурную для России пору накопилось много тревожных вопросов и дел. Предложившие царю свою покорность, гетманы запорожские снова колебались и призывали на помощь турок и крымцев. Польша неискренно относилась к перемирию, заключённому с Россией, и тайком от неё вела переговоры с турецким султаном. Большое войско посылалось на помощь к Ромодановскому, идти с ним за Днепр на гетмана правой, ещё не покорившейся, стороны Днепра — на Дорошенко, собравшего около себя в Чигирине остатки не принявшего русского подданства казачества.
Наконец молодой Стародубский получил из Разрядного приказа назначение на службу в полк Шепелева. Среди зимы 1674 года Стародубский, приняв благословение отца и поклонившись святым храмам Кремля, выступил из Москвы с отрядом, к которому был причислен. Отряд шёл, как сказано, в войско Ромодановского, стоявшего на берегу Днепра; недавно воевода прогнал за Днепр Дорошенко, опустошавшего города левобережья, и стоял теперь, ожидая помощи и новых распоряжений из Москвы. Полк Шепелева, к которому причислен был Алексей, двигался медленно по глубоким снегам, оставляя по пути в городах немало больных и ослабших на попечение местных воевод.
Продвигаясь на юг почти по всей России, Стародубский собственным опытом убеждался в непорядках, царивших на всей Руси, о которых прежде знал по слухам. Сама живая жизнь убеждает глубже, пробуждая жалость к страдающим и утеснённым. Везде, где только случалось Алексею толковать с местными жителями, были слышны жалобы на воевод. Их обвиняли в поборах, в жестокости при взимании податей с посадских людей и горожан. В городах встречались населения из одних боярских детей, а посадских почти не было, — все они разбегались, находя, что невозможно заниматься ни торговлей, ни ремеслом при постоянно возрастающих поборах. Причиной этих налогов была постоянная война на окраинах.
Посадские люди переходили на землю помещиков, закабаляли свой труд, а податей в городах собирать уже было не с кого; в казне чувствовался недостаток в деньгах.
Непривлекательные и неутешительные картины пришлось видеть Алексею и дальше, на Украйне, и на самой родине шляхтича, порицавшего так громко все русские порядки.
В древней русской столице Киеве, вновь оставшемся тогда уже за русским царём, полк, с которым шёл Алексей, расположился на отдых; город был сильно разорён частыми нашествиями; теперь в нём был русский воевода, встретивший русское войско. В Киеве, на улицах, пестрели разнообразные одежды польских панов, евреев и других иноземцев; впервые видел здесь Алексей свободно выходивших по лавкам и на прогулку польских панночек в красивых платьях, обтягивавших стройный стан.
На улицах Киева стояло ещё много развалин прежних домов, разрушенных и ещё не поправленных вновь; русские воины пошли поклониться Печерской лавре и принять благословение митрополита; монахи имели унылый вид, — они жили постоянно в страхе, опасаясь новых нашествий и разгрома.
Храмы лавры, возвышаясь на древней Печерской горе, видны были из-за окружавшей их стены и сияли золотыми куполами; глубокий овраг, поросший лесом, теперь обнажённым, безлиственным, отделял от дороги старую Киево-Печерскую лавру; окружавшие её стены местами были полуразрушены и примыкали к крепким, недавно восстановленным воротам; русские воины вошли в храм, и вместе с ними молодой Стародубский преклонился перед мощами основателя лавры, св. Феодосия; провожавший их монах провёл их также к гробнице митрополита Петра Могилы, похороненного в Печерской лавре; возвращаясь к своим квартирам, русские любовались на город, лежавший у подножия Старокиевской горы; улицы постепенно понижались по её скатам; нижняя часть города состояла в то время из бедных мазанок, наполовину разрушенных пожарами во время разгрома; в зимнее время сторона эта не представляла особенно живописного вида. Вернувшись в квартиру, Алексей наскоро пообедал и не ложился отдыхать по общему обычаю, но пошёл осматривать город; он направился отыскивать в нижнем городе древний Братский монастырь с духовной академией, о которой он наслышался в Москве, где предполагали уже устроить такую же академию и школу для детей бояр и духовенства; монахи радостно встретили русского воина и боярина, всею душой радуясь, что были возвращены под защиту русского царя и его войска; здесь показали ему храмы, а ректор академии пригласил его осмотреть здание внутри. В обширной трапезной сидел Алексей, окружённый монахами; ректор и архимандрит монастыря расспрашивали его о вестях, касавшихся войны; вместе с другими рассказами о Москве, только что им покинутой, он мог сообщить им, что знал о намерении царя окончательно покорить Украйну, не доверяя более мирным договорам и лукавым обещаниям поляков; слова его вносили мирные надежды в их встревоженные и утомлённые головы.