Нижегородским воеводой в то время был Василий Петрович Шереметев, племянник Федора Ивановича. За внимание к их людям, строившим корабль, послы поднесли ему подарок ценой в 100 рейхсталеров, или 50 рублей. Воевода оказался человеком вежливым, приветливым и державшим весьма приличную обстановку. Он пригласил посольство к себе на угощение. На дворе голштинцев встретили два человека и провели между расставленными по обеим сторонам слугами до лестницы. В передней их приняли два почтенных старика и проводили в покой, убранный коврами, занавесами, серебряными чарами и ковшами. Воевода стоял здесь, одетый в кафтан из золотой парчи и окруженный многими лицами, также в богатых кафтанах. Он сказал послам приветственную речь; потом пригласил их сесть за стол и предложил выпить за здоровье его царского величества, его герцогской светлости, а также и его посольства. Угощение состояло из медовых пряников, отличной водки и различных видов меду и сопровождалось приятными, содержательными разговорами со стороны хозяина, что немало удивило гостей, при их предубеждении в отношении к русским вообще.

30 июля голштинское посольство покинуло Нижний и поплыло вниз по Волге. Его корабль, имевший 120 футов длины, был плоскодонный, сидел в воде только 7 футов и вообще был приспособлен к плаванию по этой великой русской реке, уже тогда обильной мелями и перекатами; на случай безветрия он был снабжен 24 веслами, чтобы можно было идти без парусов. Но так как уровень воды в это время года значительно понизился, то путешественникам пришлось часто бороться с мелями, и первые дни они очень медленно продвигались вперед. Олеарий по всему пути упоминает встречные струги, плывшие снизу и нагруженные солью, икрой и рыбой, селения, видневшиеся по берегам, и небольшие города, каковы: Васильсурск, Козьмодемьянск, Чебоксары, Кокшайск и Свияжск. Эти города, снабженные обыкновенно деревянными стенами и башнями, были заняты военными гарнизонами, державшими в повиновении татар и других инородцев сего края. Спустя две недели по выезде из Нижнего путники достигли Казани. Она представляла сравнительно большой и также деревянный город, населенный татарами и русскими; но внутренний город, или кремль, был укреплен толстой каменной стеной с пушками, и ни один татарин сюда не допускался. Под Казанью голштинцы застали судовой персидский и черкесский караван, который ранее их выехал из Москвы. В этом караване находились персидский купчина, бывший посланником от шаха к царю, и черкесский князь Муцал из города Терки, получивший от царя по смерти своего брата его владение. (Этот вассальный или служилый мусульманский князь, по словам Олеария, будто бы был племянником известного Ивана Борисовича Черкасского; в действительности он приходился племянником Дмитрию Мамстрюковичу.) Воеводой казанским на ту пору был Иван Петрович Шереметев, родной брат Нижегородского. Послы поднесли ему перстень с большим рубином. Но тут корабль простоял только день с чем-то и двинулся далее.

За Казанью берега Волги сделались более пустынны; местами виднелись уединенные дворы или «кабаки», вероятно существовавшие по преимуществу для продажи крепких напитков судовому рабочему люду. От Казани до Самары, на пространстве 350 верст, путники видели только один город, Тетюши, до того незначительный, что он был окружен даже не стеной, а частоколом или тыном. Ниже его они повстречали воеводу города Терки, который плыл на восьми судах, в сопровождении сильного стрелецкого конвоя; после обычного трехлетнего воеводства он возвращался в Москву. Его стрельцы сообщили голштинцам, будто до 3000 казаков поджидают их в разных местах. Если на дальнейшем пути по Волге бороться с мелями приходилось реже и легче, зато на передний план выступила опасность от разбоя волжских казаков, и весь этот путь сопровождался постоянными страхами и всякими военными предосторожностями. Голштинский корабль был снабжен пушками, порохом, железными и каменными ядрами; для стражи заранее нанято некоторое количество солдат и вся посольская свита вооружена мушкетами, учреждены постоянные и правильно сменявшиеся караулы; таким образом, корабль всегда был готов выдержать и отразить нападение казачьих лодок с их плохо вооруженной и беспорядочной толпой. Олеарий, между прочим, указывает и на знаменитый разбойничий притон, речку Усу на Самарской луке; причем передает, что в предыдущем году казаки захватили здесь целое судно, принадлежавшее богатейшему нижегородскому купцу. Близ этой речки он видел Соляную гору, где из копей добывалось огромное количество соли, которую отправляли отсюда вверх по Волге и в Москву. (Это, по-видимому, берега соседней речки Усолки с ее соляными ключами.)

По всей вероятности, принятые голштинцами предосторожности, постоянная вооруженная сила и постоянная готовность к бою избавили их от нападения; ибо казаки-разбойники действовали с расчетом и после предварительных разведок. Так, посольство получило уведомление, что на его корабле в числе русских рабочих и гребцов замешалось четверо таких казаков. А на Овечьем броду (на пути между Самарой и Саратовом) путешественники встретили двух рыбаков, которые рассказывали, что еще за восемь дней до того ограбившие их казаки говорили об имеющем быть проходе большого корабля, принадлежащего немцам. О Саратове Олеарий замечает только, что он лежит при рукаве Волги в 4 верстах от ее главного течения и что он заселен одними стрельцами, которые оберегают край от калмыков; последние кочевали от сих мест до Яика и Каспийского моря.

Далее по пути к Царицыну голштинский корабль соединился с помянутым выше персидско-черкесским караваном, среди которого находился русский посланник к персидскому шаху. Олеарий называет его Алексей Савинович Романчиков и сообщает, что сей посланник был чиновник лет тридцати, умный, ловкий и очень любознательный, так что впоследствии, во время совместного пребывания в Персии и обратного пути, он научился у голштинцев латинскому языку и употреблению астролябии. Персидско-черкесский караван сопровождали более 400 конвойных стрельцов. Во время плавания все эти посольства, купно с князем Муцалом, взаимно посещали и угощали друг друга. Город Царицын оказался также заселенным одними стрельцами, которые держали стражу против ногайских татар и казаков и должны были охранять проходящие суда. Но и сами стрельцы терпели от разбойников. По словам Олеария, вот что случилось незадолго до прибытия голштинцев. Казаки заметили, что жены и дочери царицынских стрельцов ежедневно отправляются на один большой остров доить коров, и иногда без охраны. Тогда они выбрали удобное время, захватили женщин и подвергли насилию, а потом отослали их домой к стрельцам. В 10 верстах за Царицыном путники видели на высоком берегу виселицу, на которой местный воевода вешает разбойников-казаков. От этого города вплоть до Каспийского моря идет страна пустынная, песчаная и бесплодная, так что лежащий ниже город Черный Яр и сама Астрахань получают весь хлеб по Волге из других мест,