История формирования Бутырского полка такова. Он был создан по постановлению Земского собора, который собрался в январе 1642 года для обсуждения вопроса о предоставлении помощи донскому казачеству в обороне захваченной им турецкой крепости Азов в низовьях Дона. Ввиду недостаточной ещё мощи Московского государства, не оправившегося окончательно от внутренних неурядиц и последствий Смутного времени, Собор решил воздержаться от оказания военной помощи донским казакам. Это неминуемо привело бы к обострению отношений с Турцией, обладавшей значительной военной силой. Тогда и принял Земский собор следующее решение:
«...Направить в польские (то есть степные земли Юга), в украинские и поволжские города, на Москву и в города и по всей земле Русской ратных людей, стрельцов и солдат, сколько Государь укажет, не из крестьян и не из холопий».
Своё название «пехотный» солдатский полк получил от Бутырской слободы, в которой он размещался с 1657 года. До этого он именовался по именам своих командиров: Алцыля, затем Далеиля, Коровкова, Родиона Жданова, Алексея Бюста. Впервые полк иногда упоминается под именем Бутырского в 1685 году.
Бутырский полк в силу своей «выборности» — то есть образцовости — отличался от обычных полков солдатского строя царя Алексея Михайловича. Если в обычном солдатском полку было десять рот по сто человек в каждой роте, то в выборном полку имелось от 52 до 60 рот. Но эти роты не входили непосредственно в состав выборного полка, а, в свою очередь, каждые десять рот объединялись в свои полки (иногда в то время их называли полчками), а уже эти полки сводились в выборный полк.
Полчки выборного полка, как и большинство солдатских полков нового, европейского строя, были поселёнными. Солдаты вместе с семьями проживали в ближайших к Москве населённых пунктах и занимались ведением хозяйства. Один раз в год полчки собирались воедино на учебные сборы в каком-то одном, заранее установленном месте.
С началом военного похода полчки вливались в большой выборный полк. А после окончания военных действий солдаты распускались по домам. Но в составе выборного полка наличествовал один постоянный, всегда находящийся под ружьём, полк с полным штатом офицеров и нижних чинов. Им и командовал не полковник, а человек в генеральском звании. На такую должность и был назначен генерал Пётр Иванович Гордон.
Он получил под своё командование тысячу человек. Солдаты делились на годных и негодных для полевой, походной службы. Негодные во время войны оставались дома, в солдатской слободе для несения гарнизонной и караульной службы. Солдатское жалованье в выборном полку было меньше стрелецкого, но больше, чем в обычном солдатском полку. Но большинства привилегий, которыми пользовались столичные стрельцы, бутырские солдаты не имели.
Гордоновский полк был хорошо вооружён фузеями — кремнёвыми ружьями с багинетом или штыком, который перед рукопашным боем вставлялся в ствол, и шпагами длиной в аршин или 0,71 метра. Прапорщики и капралы (в роте было по три капральства или взвода) вооружались, как и рядовые, алебардами — боевыми топорами на трёхаршинном древке. Офицеры — пистолетами, шпагой и протазаном — особым видом короткого копья.
Кафтаны у офицеров и нижних чинов были красные. Зимой для тепла надевалась красная епанча — тип утеплённого плаща. Офицеры носили нагрудный офицерский знак.
В Бутырский полк входила музыкальная команда из 27 ротных барабанщиков и флейтистов. Команда была украшением полка, и Патрик Гордон всегда ею гордился.
Полковое знамя — белое с чёрным двуглавым орлом. Свои знамёна имели также и роты — красные полотнища с изображением центавра (кентавра).
Под началом генерала Гордона находился небольшой полковой штаб, состоявший из трёх офицеров — полковника, подполковника и майора.
Офицеров в каждой роте было по три — капитан, поручик и прапорщик. Последний отвечал за сохранность ротного знамени и заботился о больных солдатах. В роте имелись ещё сержант, подпрапорщик и фуриер. Последний был квартирмейстером и оружейником. В каждом капральстве по списку числились капрал, два ефрейтора и двадцать рядовых солдат.
Таким был выборный солдатский Бутырский полк, который принял под своё командование шотландец Пётр Иванович Гордон. Начальство над ним сделало генерала одним из главных действующих лиц в столичном гарнизоне. И даже более того — заметной фигурой в русском войске конца XVII столетия.
Пребывая в Москве, в Немецкой слободе или в Бутырках, генерал много времени проводил в царском селе Преображенском, постоянно общаясь с юным царём. Он не мог не оценить по достоинству и местоположение, и красоту Преображенского.