Между тем у царя с шахом Аббасом II были вполне дружеские отношения, они «дружили» против Оттоманской империи. Узнав о проделках Стеньки, Алексей Михайлович отправил к шаху специального посланца – немца на русской службе, полковника Пальмара. В царевой грамоте говорилось, что после заключения в 1667 г. Андрусовского мира с польским королем объявились в понизовых местах разные воровские люди и против них царь послал свое войско, чтобы побить их и разорить. «И ныне после бою и разоренья достальные воровские люди от устья Волги-реки на Хвалынское море побежали, избывая своей смерти, где бы от наших ратных людей укрытца. А наши царского величества ратные люди за ними вслед неотступно промысл чинят, и чтоб тех воров искоренить и негде б их не было. А вам бы, брату нашему Аббас шахову величеству, своей персидцкой области околь моря Хвалынского велеть остереганье учинить, и таким воровским людям пристани бы никто не давал и с ними не дружился, а побивали бы их везде и смертью уморили без пощады».
Весь июнь 1668 г. казаки провели на побережье между Дербентом и Баку, однако ни одной крепости им взять не удалось. Разинцы обошли Дербент, Шемаху и Баку. В июле казаки дошли до Гилянского залива и начали грабить богатую область Мазандеран. От успехов у атамана закружилась голова, и он повел свое воинство на крупный город Решт. Но тут казаки нарвались на войско местного губернатора Будар-хана. Как позже показали свидетели – астраханские купцы Никита Мусорин и Таршка Павлов: «Те воровские казаки приехали под шахов же город Ряш и стали стругами у берега. И ряшский-де хан выслал против их шаховых служилых людей з боем, и те-де шаховы люди их, воровских казаков, побили с 400 человек. А атаман-де Стенька Разин с товарищи говорили шаховым служилым людям, что они хотят быть у шаха в вечном холопстве, и они б с ними не бились».
Действительно, Степан Тимофеевич действовал классически, по «варяжскому рецепту» – получив отпор, нанимался кондотьером на службу.
Будар-хан согласился, но потребовал, чтобы казаки сдали персам все свои струги и пушки, а им в свою очередь будет разрешено отправить посланцев в Исфагань к шаху, который и должен был решить судьбу разинцев. А пока суд да дело, пять дней казаки торговали и пьянствовали в Реште. Согласно преданию, Степан Тимофеевич, будучи сильно во хмелю, затеял драку с горожанами, которая переросла в большое сражение. С трудом казаки пробились к морю и отбили у персидской стражи собственные струги. Выйдя в море, Разин приказал идти вдоль побережья на восток, а затем высадиться на пустынном берегу.
А шах Аббас II поначалу милостиво принял русских посланцев, но тут наконец прибыл полковник Пальмар, и шах понял, с кем он имеет дело. Немедленно разинских посланцев заковали в кандалы, а воеводе Мехмету было приказано с большим войском идти на казаков.
Приведя в порядок разбитое воинство, Стенька опять двинулся на восток и внезапно напал на небольшой город Фарабат. Он располагался примерно в 400 км восточнее Решта, и местные жители слыхом не слыхивали о Разине. Город был разграблен и сожжен. Затем Разин двинулся к расположенному неподалеку городу Астрабаду, который постигла участь Фарабата.
Зиму 1668–1669 гг. разинские казаки провели на полуострове Миян-Кале между Фарабатом и Астрабадом. Пленные персы построили деревянные дома для жилья, а также возвели земляной вал на перешейке, соединяющем полуостров с материком, и казаки поставили там пушки.
Зимой и ранней весной разинцы периодически совершали налеты на туркменские поселки на юго-восточном берегу Каспия. В одной из стычек с туркменами был убит Сережа Кривой.
Разорив туркменское побережье, Разин в мае 1669 г. двинулся на запад – в Гилянский залив. Традиционно пограбив побережье, Разин отправился севернее и устроил себе базу на Свином острове недалеко от Баку.
В июле 1669 г. к Свиному острову подошел персидский флот под началом Менеды-хана. Флот – это сказано слишком громко: у персов было 50 плоскодонных лодок-сандалов.