Илейка отличался непостоянством и то и дело менял хозяев. Он вспоминал, как «из-под юртов, от казаков, ушел в Астрахань, и в Астрахани побыл с четыре недели, а из Астрахани вышел к казакам же и пришел де яз к казаку Нагибе…». Таким образом, беглый холоп либо не сразу примкнул к повстанцам, либо был послан ими в Астрахань как лазутчик. Старый казак Нагиба стал впоследствии одним из самых видных атаманов в войске Болотникова.

Гулящий человек на Волге, боярский холоп, а потом вольный казак — такая биография была обычна для казаков. Однажды Илейке удалось побывать в Москве. Эта поездка относится к числу загадочных эпизодов его жизни. За рубежом «Петр» утверждал, что решил пробраться из Астрахани в Москву, когда там на трон взошел его «дядя» «Дмитрий». Он упросил купца Козла взять его с собой в столицу и даже открыл ему свое царское имя. В Москву он якобы прибыл на другой день после гибели «Дмитрия» (т. е. 18 мая 1606 г.) и почти четыре месяца прожил у мясника Ивана на Покровской улице.

Перед судом «Петрушка» поначалу умолчал о поездке в Москву и, лишь давая дополнительные показания, признал, что приезжал в столицу из Нижнего Новгорода и жил там от Рождества Христова до Петрова дня у церкви Владимира в Садах, на дворе у подьячего Дементия Тимофеева.

Илейка не уточнил времени поездки в Москву, но в его рассказе можно обнаружить примерно полугодовой пробел — от времени «зимовки» у Елагина и бегства под Астрахань до времени возвращения в Астрахань с воеводой Хворостининым летом 1605 г. Самозванец лишь кратко упомянул, что служил тогда «в товарищах» у Нагибы, который «отказал» его казаку Наметке, а дальше отправился вверх по Волге с казаком Неустройко.

Внезапное немногословие Илейки объяснялось тем, что в первой половине 1605 г. донские и волжские казаки приняли участие в важных событиях. Они захватили воевод в Царицыне и привезли их в лагерь Отрепьева под Орлом, а затем вместе с Лжедмитрием I вступили в Москву.

С редкой наивностью Илейка старался доказать посредством умолчаний и лжи, что он никогда не сражался на стороне Гришки. Коровин утверждал, будто на Волге присоединился к войску князя Ивана Хворостинина, якобы посланного в Астрахань Борисом Годуновым. На самом деле Хворостинин был послан в поход Лжедмитрием I против астраханских воевод, оставшихся верными династии Годуновых.

Если Илейка не перепутал дат и действительно покинул Москву в Петров день, то отсюда следует, что он вступил в столицу вместе с отрядами сторонников Лжедмитрия I, а покинул ее с Иваном Хворостининым.

Хворостинин прибыл в Астрахань в конце лета 1605 г., а затем направил казачий отряд на Терек. Илейка попал в этот отряд и вместе с терскими казаками зимовал на Тереке. Деньги, полученные на царской службе, быстро разошлись, и с наступлением весны казаки стали думать о том, где раздобыть деньги и пропитание.

Войсковой круг стал обсуждать план похода на Каспийское море, «чтоб итти на Курь реку, на море, громить турских людей на судех; а будет, де, и там добычи не будет, и им, де, было казаком к кизылбашскому Шах-Аббасу служить». В случае удачи казаки намеревались вернуться на Терек либо уйти в Персию.

Вскоре атаман Федор Бодырин собрал свой круг в 300 казаков и предложил идти в поход на Волгу. Поход в глубь России как две капли воды походил на задуманный каспийский поход. Согласно показаниям Илейки Муромца, «стали де те казаки триста человек опроче всего войска тайно приговаривати, чтоб итить на Волгу, громить судов торговых». Целью похода было грабить купеческие караваны. Но на Волге стояли многочисленные крепости с судовой ратью. Ввязываться в войну с ними казаки опасались. Поэтому они решили объявить, что среди них находится царевич Петр, который намерен идти в Москву на службу к дяде — царю «Дмитрию».

Вольные казаки помогли Лжедмитрию занять Москву, но по настоянию бояр их выпроводили из столицы. Ветераны похода не смирились с такой несправедливостью. Взбунтовавшиеся казаки роптали: «Государь, де, нас хотел пожаловати, да лихи, де, бояре, переводят, де, жалованье бояря, да не дадут жалованья». Показания «царевича Петра» не оставляют сомнений в том, что казаки решили выдвинуть из своей среды самозванца, чтобы оправдать затеянный разбой.

Кандидатами в царевичи стали сын астраханского стрельца Митька и Илейка Коровин. Оба служили у казаков в «молодых товарищах», исполняли всякую черную работу в казацких куренях.

Из двух претендентов только Илейка бывал в Москве, что и решило дело в его пользу. Так излагал обстоятельства своего избрания сам Илейка-Петр. Однако можно догадаться, что его избрание было связано также и с другими причинами. Он служил в войсках Лжедмитрия I и, может быть, участвовал в московском походе.

Затею атамана Федора Бодырина поддержал атаман Гаврила Пан. Их отряды соединились на реке Быстрой. Время было смутное, и терский воевода Петр Головин не посмел силой подавить зревший мятеж. Воевода послал «царевичу» приглашение прибыть в город, но казаки отклонили такую честь. Тогда Головин смиренно просил казаков не покидать Терек, а оставить хотя бы половину людей «для приходу воинских людей». Но казаки не послушали его и ушли войском к Астрахани. Находившийся в Астрахани воевода Иван Хворостинин отказался «для грабежу» пустить в город «царевича» и не дал мятежникам разграбить Астрахань. Но он не решился предпринять против них военные действия, тем более что многие астраханские казаки присоединились к терскому войску.

Казаки заняли четыре городка на Волге. Если бы они при этом казнили воевод. Разряды непременно бы сообщили имена погибших. Однако дело обошлось без кровопролития. Казаки повсеместно заявляли, что везут в Москву племянника «Дмитрия». Это позволило им пройти до Царицына и Самары.

От Казани навстречу терцам двигалась судовая рать боярина Федора Шереметева. У воеводы было достаточно сил, чтобы заставить мятежных казаков повернуть вспять. Но в районе Самары к «Петрушке» прибыл Третьяк Юрлов-Плещеев с грамотой. Лжедмитрий I приказал «итти к Москве наспех». Однако под Свияжском атаманы узнали о гибели Лжедмитрия I.

Войско оказалось в западне. Впереди была Москва, свергшая «Дмитрия», позади — Шереметев. Тогда казаки решили в последний раз воспользоваться услугами Юрлова. Тот явился в Казань и уверил тамошних воевод, что терское войско готово выдать им нового самозванца и принести присягу царю Василию. Усыпив бдительность бояр, казаки пробрались ночью мимо казанских пристаней и ушли к Самаре. Спустившись до устья Камышенки, казаки миновали Переволоку и укрылись в донских станицах. Там «Петр» провел несколько месяцев.

На Тихом Дону было неспокойно. Но царь Василий нашел способ замирить вольницу. По его приказу сын боярский Молвянинов 13 июля 1606 г. повез на Дон 1000 рублей денежного жалованья, 1000 фунтов пороха и 1000 фунтов свинца. Меры царя Василия достигли цели. Значительная часть донских казаков осталась в своих зимовьях и не участвовала в походе на Москву.

Повстанцы верили в то, что «Дмитрий» жив и находится в пределах России. Двое монахов-лазутчиков, засланных в «воровской» лагерь, донесли, что мятежники клялись, что сами видели царя.