С одной и с другой стороны завязались переговоры с новыми хозяевами Яика. Но так как послы, отправленные к ним царем, не добились ровно никакого результата, к концу 1667 года астраханский воевода, князь Иван Прозоровский, получил приказ отправиться в поход. Разин послал против него лишь горсть своих людей, переманил часть враждебного отряда на свою сторону, а остальных убил. Весною следующего года, получив подкрепление в лице 700 донских казаков, он вышел в море и предпринял самый славный в истории его атаманства поход.
Опустошив персидский берег от Дербента до Баку, Разин добрался до Решта. Вступив с ним в переговоры и обменявшись заложниками, наместник города, Будар-хан, открыл рейд для казацкой флотилии, и в то время как слухи об этом событии подняли всю Донскую область, Стенька стал мечтать о стоянке на персидской территории и предложил свои услуги шаху.
В таком виде это предприятие открывало перспективы, которые могли стать соблазнительными даже для Москвы. Ермак со своими товарищами начал совершенно таким же образом покорение Сибири, с той только разницей, что те не встретили там правильно организованной власти, с которой правительство их страны находилось бы в определенных отношениях. Шах и предложения, которые ему делал Разин, только портили дело. Между тем в Кремле не отчаивались уладить дело, если бы только Стенька с товарищами не поставили себя в такое положение, при котором какой бы то ни было компромисс с ними и с их действиями и поступками был совершенно не возможен. В Реште они повели себя таким образом, что восстание жителей принудило их быстро покинуть город, оставив на месте 400 человек.
Они устроили ужасную месть в Ферабаде. Явившись туда сначала под видом людей с самыми мирными намерениями и с целью будто бы завязать коммерческие сношения на местном рынке, они потом неожиданно набросились на доверчивое население. Весною 1669 года они продолжали свою месть, вернувшись на восточный берег Каспия с целью грабежа туркменских улусов. Набросившись затем на персидский флот, они нанесли ему полное поражение. Персидский адмирал, Менеди-хан, едва убежал с тремя галерами, оставив в руках победителей сына и дочь, которую Стенька сделал своею любовницею.
Воспоминание об этом походе сохранилось в одной казацкой думе, где Разин имеет сотоварищем по оружию Илью Муромца, эпического героя национального мифа, современника Владимира!
Но уже настоящая эпопея казацкого атамана приняла опасный оборот. Переговоры с шахом не привели ни к чему и победоносные, но истощившие все свои усилия и неспособные дольше продержаться на море и прокормиться на нем, Стенька с товарищами не знали, ни что им делать, ни как поступить с награбленною ими богатою добычею. В глубине души, следуя своим наклонностям, они охотно закончили бы эту авантюру обычной и тривиальной развязкой казачьих набегов по Черному морю: возвращением в донские станицы с пожитками убитых и ограбленных «нехристей». Но они имели неосторожность бравировать перед московским правительством, и путь к отступлению был им отрезан. Решившись в свою очередь отомстить и приготовившись на этот раз получше, астраханский воевода поджидал их на дороге с 36 галерами и 4000 стрельцов.
Плохо осведомленный и всегда неосторожный Стенька натолкнулся на эту огромную силу, должен был отступить и, преследуемый, заключил капитуляцию. Прозоровский, соблюдая данные ему инструкции, показал себя склонным к примирению. Казаки соглашались отдать все то, что они некогда забрали как на мусульманской территории, так и в других местах, а разграбление берегов Каспийского моря могло сойти за законную репрессию за набеги на прибережные московские владения, которым они подвергались периодически со стороны подданных или данников Персии. Был заключен на этом основании трактат. 25 августа 1663 года Стенька со своими товарищами торжественно подписали акт подчинения в городской думе Астрахани. Атаман сдал свою булаву, подтвердил клятвою выполнение принятых на себя обязательств и послал в Москву депутацию, которая получила лишь снисходительный выговор.
Затем он стал пировать с воеводами, одарил их богатыми персидскими материями, бил челом царю от покоренных городов во владениях шаха и добился того, чего хотел: позволения вернуться на Дон с остатками добычи. Обещав выдать свою артиллерию, он сохранил для себя двадцать пушек, в которых, как он утверждал, он настоятельно нуждался, чтобы переходить с ними степь и держать в страхе крымских или азовских татар и турок.