Возможность проверить на прочность новое политическое устройство и испытать в деле недавно созданные полки «нового строя» представилась Русскому государству уже очень скоро. В 1648 году гетман Войска Запорожского Богдан Хмельницкий поднял восстание против Речи Посполитой. Причиной этого стали глубокие религиозные, социальные и военные разногласия между украинцами и Польшей, главной половиной федеративного государства Речь Посполитая, в которое входила и территория нынешней Украины. Поначалу Хмельницкому удавалось одерживать верх над плохо организованными и политически разрозненными польскими силами, однако постоянно сохранять единство и побеждать казаки не могли. Хмельницкий обратился за помощью в Москву. После нескольких лет колебаний русское правительство в 1654 году заключило с казаками Переяславский договор и взяло территории Гетманщины под свою защиту. В результате этого между Русским государством и Речью Посполитой началась война за Украину, которая длилась много лет и вскоре затронула и другие державы Восточной Европы. Победы русских на начальном этапе Тринадцатилетней войны и вторжение России в Литву привели к вступлению в этот конфликт Швеции. Началась вторая Северная война (1655–1660) между Русским государством, Швецией и Речью Посполитой за господство на Балтийском море и его юго-восточном побережье. После того как в 1660-х годах боевые действия в Украине стали затухать, преодолевшая кризис Османская империя заключила союз с недовольными элементами казачества и вторглась в Польшу и Украину.
Собственно Тринадцатилетняя война (1654–1667) между Русским государством и Речью Посполитой завершилась подписанием Андрусовского перемирия. Вышедшая из этой войны победителем Россия вернула себе утерянные в Смутное время огромные территории от Смоленска до Чернигова, а также получила часть Витебского воеводства, Левобережную Украину и – во временное владение – Киев. Потерпевшая сокрушительное поражение Польша сохранила за собой только Правобережную Украину. Такое разделение Украины на две части и сложная геополитическая обстановка этого региона привели к тому, что условия Андрусовского перемирия соблюдались недолго. Напрямую или опосредованно Москва продолжала воевать в Украине с турками, поляками и другими сторонниками казачества до самого конца XVII столетия. Таким образом, возрождение имперских амбиций Русского государства происходило на фоне непрекращающихся боевых действий.
Тринадцатилетняя война коренным образом преобразила военное устройство России. Опираясь на прежний опыт и задействовав новоприобретенный политический капитал, русское правительство разработало бюрократические механизмы, которые позволили ему в кратчайшие сроки избавиться от некоторых элементов военной организации, унаследованных от степного войска. Теперь в русской армии было множество полков «нового строя». Во многих из них офицерами служили европейские наемники – профессионалы, квалификация которых позволила трансформировать степную конницу и прочие войска в армию «нового строя»; небольшое количество новых офицеров были русскими. Важную роль в вооруженных силах Русского государства стала играть пехота (солдаты), ряды которой регулярно пополнялись за счет сборов даточных людей. Старая поместная конница с ее разделением на сотни постепенно лишилась своего прежнего влияния, и все больше детей боярских и бедных дворян поступали на службу в кавалерийские полки «нового строя» (рейтары). Эти новые боевые части получали поддержку со стороны правительства – административную и отчасти материальную, и финансовую. Хотя до самого конца Тринадцатилетней войны структура верховного командования армии оставалась прежней, к концу 1660-х годов в Русском государстве уже полным ходом шло реформирование военного устройства страны.
Одновременно с процессом реформирования резко увеличилась и численность русской армии. Перед Москвой стояло сразу несколько военных задач: содержание гарнизонов в крепостях на границе со степью, в Сибири и форпостах на западных рубежах, а также ведение войны на нескольких фронтах. Более того, людские потери в Тринадцатилетней войне были очень велики. И тем не менее русскому правительству успешно удавалось довольно быстро набирать в действующую армию все большее количество солдат.