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