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