Но и московское правительство еще времен царя Михаила почувствовало всю непригодность войска стрелецкого устройства для борьбы с регулярными отрядами, нанятыми польским правительством в Германии для войны с Москвой; особенно беспомощны были стрельцы и служилая конница при столкновении с превосходно организованной и вооруженной армией шведского короля Густава-Адольфа. Правительство царя Михаила испробовало сначала по польскому образцу нанять на свою службу отряды охочих воинских людей за границей. В тогдашней Европе после ожесточенных религиозных войн конца XVI века было много таких продажных шпаг, владельцы которых не знали другого ремесла, кроме военного, и охотно шли за приличное вознаграждение на службу к иноземным государям. Предприимчивые генералы и полковники собирали целые отряды, во главе которых и нанимались на службу к тому государю, который в такой воинской услуге нуждался. Но наем стоил дорого; наемники не всегда были верны нанимателю, и московское правительство очень больно почувствовало ненадежность служилых немцев во время неудачной осады Смоленска в 1627 году, когда наемные немецкие отряды передались на сторону неприятеля. Тогда в Москве пришли к мысли завести свои полки регулярного строя, пешие – солдатские и конные – рейтарские и драгунские, в которых все солдаты, унтер-офицеры, а по возможности и офицеры были бы из своих русских людей. Порешили нанять за границей достаточное количество высших и низших офицеров, немного обученных солдат и поручить им устроить полки иноземного строя из русских людей.
Иностранцы в порядочном количестве проживали в Московском государстве со времен Бориса Годунова, который не только призывал на русскую службу знающих и военное дело и разные мастерства иноземцев, но и посылал своих людей учиться за границу. За время Смуты вместе с польскими и шведскими войсками вошло в Россию и осталось в ее пределах на житье немало иностранцев. В 1614 году в военный поход шли роты иноземцев «старого выезда». В 1628 году в большом полку в Туле были роты иноземцев: поляков и литовцев ротмистра Рогоновского, немцев с ротмистром Денисом фон-Визеном – это предок знаменитого автора «Недоросля» и «Бригадира»; была рота «бельских немцев» – это отряд немцев, находившихся в польской службе гарнизоном в крепости Белой; они не только сдали крепость, но сами перешли на русскую службу; были отряды из греков, сербов, волохов. Словом, когда правительство царя Михаила начало заводить русские регулярные полки, то недостатка в кадрах и инструкторах не было. Но все же решили нанять учителей получше и в 1631 году послали полковников Лесли и фон-Дама в Швецию, Голландию, Данию и Англию нанять на русскую службу ученых офицеров и обученных рядовых, «военных полковников и добрых бывалых капитанов и поручиков». Посланным, между прочим, наказали «нанимать солдат шведского государства и иных государств, кроме французских людей, а францужан и иных, которые римской веры, никак не нанимать»: воины римско-католического исповедания казались в Москве неудобными для борьбы с католической Польшей. Особой грамотой к датскому королю царь Михаил просил короля Христиана «для нашие царские дружбы и любви поволити в своем королевстве и в землях, которые ныне за вами, ратных людей полковнику Александру Лесли наймовать, а которые похотят наимоватца и иных государств люди и тех бы вам наемных людей через свое государство, через Зунд и в иных местах, где им лучица идти, велеть пропускать без задержанья и на корабли посадить»… Лесли и фон-Дам вывезли около 7000 иноземных воинских людей на русскую службу. Устройство полков иноземного строя из своих тоже шло своим чередом. Еще в Смоленском походе были такие полки из русских людей, «написанных к ратному учению», с иностранными полковниками, майорами и ротмистрами во главе.
При царе Алексее Михайловиче вызов иностранного офицерства в Россию продолжался, продолжалось и устройство русских полков иноземного строя. После тридцатилетней войны в Европе было много военного люда без денег и без дела, а потому нанимать было из кого; английские и шотландские смуты половины XVII века тоже вытолкнули на русскую службу немало опытных и знающих солдат и офицеров. В 1658 году полковник Франц Траферт был отправлен за границу для найма на русскую службу военных инженеров. Другой иноземец, Гебдон, должен был подыскать в Голландии опытного генерала, способного командовать большой армией. В 1661 году приехали на русскую службу майор Патрик Гордон и капитан Павел Манезиус, оба шотландцы, англичанин полковник Диккенс, много немцев, датчан. В 1651 году охотился поступить на русскую службу лорд Чарльз Эргарт, «губернатор оксфордский и начальник всей английской кавалерии», но только условия он ставил не совсем подходящие для русского правительства; он требовал звания генералиссимуса, неограниченной власти в суде и расправ над воинскими чинами и права производства во все чины, не исключая генеральских. На таких условиях, конечно, договор не состоялся, а на меньшие пышный лорд не соглашался. В 1660 году царь Алексей особой грамотой просил английского короля Карла II разрешить нанять в Англии на русскую службу 3000 конных и пеших ратных людей с офицерами. С разрешения короля и парламента наняты были тогда в Лондоне «комишариушем» Гебдоном генерал князь Вилим Келетрав, полковники, офицеры и 3000 рядовых.