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