Так разбойничья эпопея переросла в войну с государством.
Разин повел своих людей обратно к Волге и скоро соединился с атаманом Василием Усом, который давно уже собирал к себе беглых крепостных и воевал с царскими воеводами. Теперь в войске насчитывалось около семи тысяч человек.
Степан хорошо понимал, что одними казаками Россию не одолеешь, и, вслед за Усом, стал звать к себе весь черный люд. Разинские посланцы отправились по соседним областям, всюду объявляя, что грядет освобождение от власти злых бояр, взявших в неволю батюшку-царя. Для пущей солидности врали, что в казачьем войске находится царевич Алексей Алексеевич (на самом деле недавно умерший), а также патриарх Никон. Про последнего в народе было известно, что он чем-то не угодил боярству, а потому наверняка пострадал за правду. Добравшись до Волги, повстанцы даже обустроили два особых судна: обитое черным бархатом для патриарха и обитое алым бархатом для царевича (последнего изображал какой-то черкесский пленник). Это было отголоском сохранившихся воспоминаний о Смуте, когда самозванство использовалось для легитимизации антиправительственных движений.
Первоначальный план Разина казался грозным и простым: взять Царицын, оседлать волжский путь, а затем двинуться по нему вглубь Руси, используя реку в качестве основной коммуникации и пополняя ряды войска за счет местного населения.
Царицын достался легко. Там сидел новый воевода, Тимофей Тургенев, который хотел биться до последнего, но царицынцы, как горожане, так и стрельцы, памятуя о недавнем веселом гостевании разинцев, распахнули ворота. Воевода заплатил за свое упрямство жизнью.
Несмотря на то что правительство давно уже ждало от Стеньки неприятностей, казачий поход все же застал власти врасплох. Первые попытки подавить бунт выглядели беспомощно: с верховьев Волги на Царицын двигался отряд Ивана Лопатина в тысячу стрельцов, а с юга князь Львов вел две с половиной тысячи астраханцев.
Разин сначала разбил меньший контингент, но те хоть оказали сопротивление, а вот астраханские стрельцы, симпатизировавшие Стеньке, все перешли на его сторону без боя. От радости атаман даже помиловал их начальника князя Львова (позднее его, правда, все равно убили).
До сего момента восстание шло от успеха к успеху, и, если бы Разин остался верен прежней стратегии, очень вероятно, что он дошел бы до Москвы и в стране началась бы новая Смута – «третье» российское государство, как мы видели, было не слишком прочным. Но атаман передумал.
Он рассердился на астраханского воеводу Прозоровского, а хорошо знакомый город представлялся легкой и богатой добычей. Вместо того чтобы идти на север, Разин повернул на юг – это решение предопределило поражение так триумфально начавшегося дела.