Прежние роты иноземцев в значительной степени перетасовали, с тем чтобы в каждой из них было примерно по сто человек; в эти сотни подбирали по возможности воинов одной национальности. «Меньшинства» распределяли так, чтобы языком и обычаями они не очень отличались от основной народности сведенной роты. В результате перетасовок число рот увеличилось до одиннадцати. В некоторых ротах поменялись ротмистры — их выбирал личный состав.

Командиром иноземного воинства на службе у русского царя назначили приехавшего в 1631 году полковника Александр Лесли — шотландского дворянина, отец которого сражался под знаменам шведского короля Густава-Адольфа II и достиг звания фельдмаршала. По царскому повелению в 1632 году полковники Александр Лесли и Пецнер, а по смерти последнего Генрих Ван Дам сформировали четыре пехотных полка и один кавалерийский, рядовой состав в которых назывался «солдатами».

Главной задачей Лесли и его помощников было создание кавалерии, способной достойно оппонировать польским гусарам — главной ударной силе предполагаемого противника. За образец выбрали незадолго перед тем появившихся на полях сражений рейтар — особый род конного войска, происходивший от наемных кавалерийских отрядов, отменно проявивших себя в ходе Тридцатилетней войны. В отличие от всех прежних родов кавалерии, основу вооружения рейтар составляло огнестрельное оружие — помимо аркебузы или мушкета у каждого были пистолеты в седельных кобурах. Если же дело доходило до рукопашной схватки, то рейтары пускали в ход меч — оружие, сочетавшее лучшие качества сабли и шпаги: длинный, прямой, узкий, обоюдоострый клинок, которым можно было и рубить, и колоть. Первым московским рейтарским полком командовал француз шевалье Шарль де Эберт. Набирали в рейтары только молодых людей из лучших московских фамилий.

Для того чтобы вооружить русских рейтар, Лесли и Ван Дам совершили вояж в Европу, где на казенные деньги были произведены закупки вооружения, главным образом лучшие образцы пистолей и мушкетов. Кроме прямых закупок были сделаны большие заказы разным европейским фирмам. Для налаживания производства собственного оружия голландскому предпринимателю Виниусу, который вел торг хлебом в Московии, было разрешено основать близ Тулы железоделательные заводы. Также предполагалось, используя связи Лесли среди шведских военных, навербовать побольше солдат-наемников. Но сделать это не удалось, так как еще продолжалась Тридцатилетняя война и каждый шведский солдат был на счету у себя дома. Из-за трудности найма солдат Лесли и Ван Дам смогли только на треть укомплектовать полки «иноземного строя» профессионалами-наемниками, которым была отведена роль инструкторов. Две трети состава полков были набраны из русских добровольцев, получавших за службу деньги. К 1633 году в новом войске уже было 9500 человек. В его рядах оказались и предки классиков русской литературы Георг Лермонт и Денис Фон Висин (тезка своего отца — ротного командира в Большом полку) — оба служили в рейтарском полку де Эберта, состоя в чине ротмистров.

Дед Дениса Фон Висина-второго — барон ордена меченосцев Берндт фон Висин (в Московии ставший Петром Владимировичем) был взят в плен во время Ливонской войны. Позже, как и многие другие пленные, он поступил на службу русской короне, премного отличился и был награжден поместьями. Шотландец Джордж (Георг) Лермонт происходил из «бельских немцев»; в 1618 году, состоя в чине прапорщика, он сражался с войсками королевича Владислава и гетмана Ходкевича под Можайском и в Москве, у Арбатских ворот. За отличия в 1621 году его пожаловали поместьями в Галиче, и он продолжил служить, состоя в ротах, подчиненных Украинному разряду. В 1632 году ему поручили обучать «хитростям ратным в конном строю» детей боярских, а также немцев и татар.

Несмотря на, казалось бы, тщательную и продуманную подготовку, дебют нового войска получился неудачным, как и вся военная кампания, во время которой он состоялся. Полки Лесли и де Эберта в составе войска воеводы боярина Шеина отправились воевать с поляками под Смоленск, но не оказали того решающего влияния на ход боевых действий, которого от них ожидали. В конце 1633 года рейтарский ротмистр Георг Лермонт вместе со многими своими товарищами сложил голову где-то под Смоленском. После этого войско «иноземного строя», признав его «не оправдавшим доверия», расформировали. Рейтарский полковник де Эберт в скором времени покинул Московию, а вот пехотные полковники Александр Лесли и прочие остались на русской службе; они очень пригодились десяток лет спустя, когда была предпринята новая попытка создания русских воинских частей европейского образца.

В 1642 году в Москве решили, выбрав из московских стрельцов лучших, свести их в два новых солдатских полка, по способу формирования названных «выборными». В каждом полку было четыре десятка офицеров-иноземцев и больше тысячи солдат. Для постоя новому войску отвели Бутырскую слободу, даровав личному составу значительные льготы: кроме шедшего им казенного денежного жалованья и провианта солдатам разрешалось заниматься огородничеством, разными промыслами, открывать лавки и любые другие торговые заведения, не платя никаких пошлин. За это служивые обязаны были в мирное время учиться «иноземному строю», стрельбе из мушкетов, нести службу в городских караулах наравне со стрельцами, а во время войны беспрекословно идти, куда направят воеводы, исполняя роль ударной силы на поле боя. Конечно, этих двух полков было явно недостаточно, и их создание можно назвать еще одним экспериментом, но нельзя не признать, что теперь для этого имелась значительная материальная база. За десять лет, прошедших с той поры, когда голландскому купцу Виниусу были даны привилегии на основание железоделательных заводов, он в значительной степени расширил дело и вместе с другим голландским предпринимателем, Исааком Аменом, и его зятем, гамбургским купцом Петром Марселисом основал промышленную компанию. Эта компания получила привилегию на строительство железоделательных заводов и вдобавок к тульским основала новые — на Шексне, под Костромой, в Олонце. Для работы на этих заводах было приглашено более 600 мастеров из Голландии и Германии: литейщиков, кузнецов, шпажников, оружейников, слесарей и строителей плотин, необходимых для устройства водяных двигателей, которые обеспечивали работу заводских механических молотов и иных устройств.

По-настоящему формировать новую армию стали при Алексее Михайловиче, занявшем трон в 1645 году. Новому государю было только шестнадцать лет, но у него имелись очень дельные советники, которые, ни секунды не сомневаясь, продолжили политику прежнего правления — тем более что эксперимент с «выборными» полками, похоже, был признан удачным.

Царский тесть, боярин Илья Данилович Милославский, побывавший с посольством в Голландии, пригласил на русскую службу полковника Исаака ван Бокховена с сыновьями Корнелиусом и Филиппом. Вместе с ними в 1647 году приехали десятка два опытных голландских и немецких офицеров, которые совместно с «московскими старожилами» — полковником Александром Лесли, Александром Кроуфордом и Иоганном Бутлером — собрали еще два элитных полка. Руководившие новым войском Бокховены превратили новые части в подобие военного училища; поэтому через рядовой состав этих полков прошло немало отпрысков благородных фамилий. Офицеры-иностранцы обучали русских солдат сражаться в конном и пешем строю, действовать пикой, атаковать сомкнутым строем, стрелять залпами, чем достигалась большая плотность огня. Скорострельность зависела от слаженности действий при движении в плотном строю. Поэтому строевая муштра сделалась важнейшим элементом боевой подготовки. Офицеры с палками в руках нещадно гоняли солдат на плацу, уча их безукоризненно точно и быстро двигаться, делать повороты, смыкать и размыкать строй, рассыпаться в цепь, перестраиваться по сигналам. Необычайное значение приобрели военные музыканты: их игра не только поднимала дух воинов и давала ритм движениям, они еще и выступали в качестве сигнальщиков, когда в грохоте боя голос командира уже трудно было разобрать.