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