Одним из таких воевод был Степан Кузьмин, на судне которого прибыл в Терку летом 1603 года Илейка, ставший теперь городовым казаком. Жизнь в Терке не могла ему понравиться — место было низкое, заболоченное, как и в Астрахани; летом здесь стояла изматывающая жара, так же пекло солнце, разве что пыли не было. Зато река почти пересыхала, вода застаивалась. Да и скучно было, тянуло назад, в шумный нижневолжский город с его базарами и белыми стенами кремля, пусть и отражающими жгучие солнечные лучи и слепящими глаза. Впрочем, именно в Терке Илейке представился шанс повысить свой статус, перейдя в категорию служилых людей.
Летом 1604 года русское правительство затеяло на Кавказе большое военное предприятие. Еще в 1586 году царь Кахетии Александр попросился в русское подданство, надеясь, что оно избавит его народ от опасности со стороны персов и турок. Царь Федор Иванович (точнее, правитель Борис Годунов) принять грузин под свою высокую руку соглашался, но в военной помощи категорически отказал — воевать из-за Кахетии с Турцией и Ираном было глупо. Тогда Александр предложил русским хотя бы разорить Тарковское шамхальство и передать ему столицу кумыков город Тарки. Для этого он обещал прислать военную помощь. Когда появилась Терка, Москва, наконец, получила возможность выполнить просьбу царя Кахетии и в 1594 году организовала экспедицию на Тарки, располагавшиеся на берегу Каспия, в верстах семидесяти южнее русского форпоста на Тереке.[4] Поход закончился катастрофой во многом потому, что «робкие грузины» так и не решились выступить на помощь русским. В Терку вернулась едва ли четвертая часть русского воинства. И вот, спустя десять лет, Борис Годунов решил повторить попытку поставить Тарки под свой контроль, понимая, что пока шамхальство на Каспии существует, Кахетия не сможет вырваться из персидской зависимости. Правда, для начала русский царь попытался договориться с шахом о передаче Тарковского шамхальства под власть Москвы по-доброму, завлекая персов перспективами союза против турок. Однако поняв, что воевать с турками по-настоящему русские не собираются, персидский шах ни на какие уступки на Кавказе не пошел. Оставалось действовать силой.
В Астрахань прибыло несколько стрелецких полков. Война с горцами серьезно финансировалась — на «шевкалской» (то есть «шамхальский») поход было выделено 100 тысяч рублей. Из Астрахани войска переправились в Терку, где были усилены местными стрельцами и городовыми казаками. Вообще, учитывая специфику удаленной от Центральной России службы, большой разницы между теми и другими не было. Но все-таки стрельцы считались «государственными», служилыми людьми. И надо же такому случиться, что у стрелецкого пятидесятника Пятого Муромца заболел племянник и его место для участия в походе освободилось. Тут-то и помогло Илейке муромское происхождение — земляк пристроил его на службу вместо расхворавшегося родственника. Так Илейка Муромец стал стрельцом и приобрел право на получение соответствующего государева жалованья.
В Терку подтянулись вольные казаки — терские и гребенские, так что общая численность русских ратных людей достигла десяти тысяч. Командование царь возложил на воевод окольничего Ивана Михайловича Бутурлина и Осипа Тимофеевича Плещеева. Опытный старик Бутурлин был назначен старшим. Пройдя через Сулак, крепость, в которой русские под руководством князя Владимира Тимофеевича Долгорукова держались еще с 1592 года и которая располагалась всего в 15 верстах от цели похода, Бутурлин привел свои силы к Таркам и приступил к их осаде. В Тарках были сосредоточены значительные силы. Город как бы сползал к морю по склону горы Тарки-Тау, напоминая своеобразный амфитеатр — каждый следующий ряд домов возвышался над предыдущими. На самой вершине горы стоял дворец шамхала, неподалеку от него — две каменные башни, из которых великолепно простреливались окрестности. У обороняющихся не было недостатка в пище и, главное, воде — горная ключевая, посредством подземных труб она поступала в крепость, где скапливалась в специально устроенных для этого резервуарах. Томить Тарки осадой не было смысла, штурмовать город можно было только в лоб — по склону, с трех других сторон столицу шамхальства окружали неприступные скалы. Бутурлин разделил свои силы на две колонны — одну, в которую входили стрельцы, он возглавил сам, вторую, состоявшую из детей боярских (дворян) и казаков, поручил Плещееву. Сломив сопротивление кумыков, русские ворвались в город и заняли его. Шамхал Анди-Хан, древний старик, почти слепой, сумел уйти в горы и укрыться у аварского хана.
Бутурлин постарался укрепиться в прибрежной местности. Уже к моменту захвата Тарков русские сожгли Эндери, заняли Истису и Качкалыковский хребет. Теперь удалось занять озеро Тузлук, лишив неприятеля источника соли, селитры и серы. Последние два компонента, как известно, являются важнейшими для производства пороха. Область кумыков оказалась, таким образом, под полным контролем русских. Удалось также обеспечить сообщение с Теркой и Астраханью. Теперь нужно было дождаться грузин, ведь царь Александр опять обещал выслать помощь. Не очень доверяя его обещаниям, царь Борис Федорович отправил в Кахетию посольство под руководством думного дворянина Михаила Татищева и дьяка Андрея Иванова, которое должно было контролировать исполнение союзниками взятых на себя обязательств. Помимо этого Татищеву предстояло решить еще одно, довольно деликатное дело — подыскать среди грузинских царевичей и царевен жениха дочери Годунова Ксении и невесту сыну Федору. Но послы не застали Александра дома — он был вызван к персидскому шаху. Оставалось ждать.
Между тем наступили холода, и Бутурлин принял решение зимовать в Тарках, которые были дополнительно укреплены — верхние башни соединили каменной стеной, а внизу, на спуске возвели новые башни, выкопав вокруг них рвы. Однако вскоре стало понятно, что спокойно зазимовать здесь не удастся — в крепости начался голод. Почему при таком щедром финансировании предприятия не было сделано необходимых запасов, так и осталось загадкой. Наладить поставки провианта на месте не удалось — окрестное население было настроено враждебно. И тогда Бутурлин принял решение пока не поздно разделить армию, отправив на зиму половину стрельцов и казаков в Астрахань и Терку. Когда этот отряд выступил из Тарков, новый шамхал Султан-Мут, энергичный сын отказавшегося от власти Анди-Хана, попытался уничтожить отступающих, напав на русских из засады. Но тщетно: бой продолжался целый день, и стрельцы и казаки отразили натиск неприятеля. Среди тех, кто сумел вырваться из Тарков, был и Илейка Муромец, к тому времени уже пожалевший о своем решении поступить на стрелецкую службу. Выступать в Тарки весной, как то предназначал для ушедших Бутурлин, молодой человек не собирался. Стрелецкую службу он бросил и, чтобы не помереть с голоду, а заодно уж точно избежать возвращения в строй, сразу же по прибытии в Терку записался в холопы к некому Григорию Елагину. У него и зазимовал.
Те же, кто остался в Тарках с Бутурлиным и Плещеевым, провели тяжелую зиму, довольствуясь остатками толокна да вяленым мясом. А по весне Султан-Мут, получивший помощь от соседей и турок, значительно усилившийся, взялся за русских всерьез. Прежде всего, он сумел выбить русские гарнизоны из крепостей, обеспечивавших связь Бутурлина с Теркой. Даже Владимир Долгоруков, сидевший в своей крепости на Сулаке более десяти лет, был вынужден сжечь ее и, пробившись к морю, на кораблях эвакуироваться с остатками своего гарнизона в Терку. Нормальное сообщение с Россией было прервано. Напрасно Бутурлин ждал возвращения войск из Астрахани — не до него теперь стало астраханским властям.
Осенью 1604 года в пределы России из Польши вступил отряд вооруженных наемников под предводительством широкоплечего рыжего молодца, именовавшего себя чудесно спасенным царевичем Дмитрием Ивановичем. Как известно, его появление имело катастрофические последствия и для молодой династии Годуновых, и для всей Русской земли в целом. Началась Великая Смута, города и села, бояре и воеводы, наконец, каждый русский человек должен был определиться, с кем он — с царевичем или с царем? Весной 1605 года Астрахань была блокирована волжскими и донскими казаками, поддержавшими мнимого сына Ивана Грозного. Помощь оттуда в Тарки подойти не могла. До последнего момента Бутурлин и его бойцы надеялись на то, что грузины выполнят свое обещание и пришлют им войско. Увы, даже если бы царь Александр решился на это, он вряд ли сумел бы воплотить свое решение в жизнь. В марте 1605 года царь Кахетии и его старший сын Юрий были убиты вторым сыном грузинского государя Константином, принявшим ислам и решившим в своей политике ориентироваться на Персию. Человеку, отправленному от русского посла Татищева разузнать, что за шум и стрельба доносятся из царского дворца, Константин показал отрезанные головы Александра и Юрия и сообщил, что подобные события в здешних краях — явление обычное. Константин стал новым царем Кахетии. Михаил Игнатьевич Татищев со своими людьми сумел благополучно выбраться с Кавказа. Судьба же Бутурлина сложилась иначе.
Оказавшись в осаде двадцатитысячного войска, которое привел под Тарки Султан-Мут, русские не проявили паники. Хорошо организованная оборона не позволяла кумыкам, аварцам и всем, кто пришел на помощь шамхалу, приблизиться к укреплениям. Но после того, как осаждающим удалось взорвать одну из городских башен, убив лучших русских стрелков, положение крепости заметно ухудшилось. Поэтому, когда Султан-Мут предложил переговоры, Бутурлин и Плещеев, реально оценив шансы отстоять Тарки силами своего изнуренного воинства, согласились договариваться. Русские предлагали оставить Тарки на следующих условиях: Султан-Мут отводит свои силы от города и позволяет им беспрепятственно уйти за реку Сулак. Учитывая, что передвигаться с больными и ранеными отступающим затруднительно, горцы должны взять на себя заботу о них, а затем отправить выздоровевших в Терку. Кроме произведенной шамхалом клятвы на Коране, обеспечением последнего условия стала жизнь сына Султан-Мута — его он передал Бутурлину в качестве аманата (заложника). Отпрыску правителя кумыков предстояло возвратиться в Тарки, только когда последний русский достигнет Терека. Шамхал соглашался на всё и, твердо веря в то, что обман неверного — вовсе не обман, а где-то даже и благо, отправил к воеводам под видом своего сына какого-то безродного бедняка, осужденного за разбой на смерть и получившего помилование на условиях участия в рискованной игре. Соглашение отметили пиром, который дал Бутурлин. Горцы отступили, а русские с песнями и под грохот бубнов вышли из проклятых Тарков.