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