Отбыла станица в Москву в ноябре 1658 года, но не добрался сразу вместе с казаками Степан до стольного российского города, занемог в пути, отстал в Валуйках.
Двинулся на Москву Наум Васильев с товарищами на ямских подводах, а Степан залежал в городке, на дворе знакомого торгового человека. Потом обмогся и пришел в съезжую избу бить челом воеводе валуйскому Ивану Языкову о пропуске его, Стеньки, на Москву вслед за станицей.
Не сразу ответил воевода, поначалу покуражился, потом послал отписку в Москву великому государю. И писал воевода так: «Мне, холопу твоему, на Валуйке в съезжей избе подал челобитною тот донской казак Наумовой станицы Васильева Степан Разин, а в челобитной ево написано, чтоб ты, великий государь, пожаловал, велел ево с Валуйки отпустить к тебе, великому государю, к Москве. И по твоему великого государя царя и великого князя Алексея Михайловича указу я, холоп твой, тово донского казака Наумовой станицы Васильева Степана Разина на твоей великого государя на ямской подводе с Валуйки отпустил к тебе, великому государю, к Москве».
Запоздал Степан Разин в Москву, но ненадолго. Застал он свою станицу в Москве. Долгие переговоры вели казаки с московскими думными людьми: сообщили, что собирается ставить крымский хан каменные городки по устью Дона и Донца, что ногаи грозят подняться из своих кочевий, а калмыцкие тайши неспокойны. Просили атаман Наум Васильев со товарищи помочь ратными людьми, огненным боем, всякими припасами и деньгами.
Впервые пришел Степан в кремлевские палаты, смотрел из-за спины атамана на великих людей московских, на бояр — князя Ивана Алексеевича Воротынского, Никиту Ивановича Одоевского и иных больших людей. Видел также воеводу князя Юрия Алексеевича Долгорукого и стрелецкого голову Артамона Матвеева.
Говорил Долгорукий казакам, чтобы поменьше воровали на Дону, а побольше бы помышляли о государевой службе и ловили бы сами и унимали воров всяких и беглых, и еще говорил князь Юрий, чтобы готовились казаки к походу под литовские города и под Киев. Молчали казаки, не хотели спорить с первым воеводой московским — больно уж долго помнил зло боярин, но и в поход идти на север от родных мест не хотели. Крутился Наум Васильев, указывал на крымскую и ногайскую опасность. Так и не договорились ни о чем казаки. Правда, обещала Москва помочь жалованьем. А ратных людей не давала — нужны были те люди на литовских рубежах.
Перед обратной дорогой был казакам отпуск у великого государя. Принимал Алексей Михайлович станицу в Набережной палате. Встреча казакам была самая обыденная — не то что большим иноземным посольствам. Царь сидел на троне в русском саженном платье, со скипетром в руке и в царской шапке. Вокруг сидели бояре в скарлатном платье, за царским троном с каждой стороны стояли рынды с топориками серебряными. Близко к царю и к руке допустили только войскового атамана, остальным дозволили смотреть издалека. Царь был молод, но тучен и благолепен.
