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