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