Он отправился в путь вместе с сыновьями и к 1733 году достиг страны вымерших ныне манданов на той территории, которая теперь называется Северной Дакотой. У тех людей, которых Верандри принял за белых, была необычная культура, разительно отличавшаяся от культуры окрестных индейских племен. Здесь Верандри нашел камень с надписями, не поддающимися расшифровке, и отправил его в Монреаль. Позднее в Париже эксперты пришли к заключению, что это татарские надписи. Однако вряд ли это возможно, так как татары и монголы совсем не занимались мореплаванием. Древнее тюркско-татарское руническое письмо очень сходно с древнескандинавским, и сторонники скандинавского происхождения майданов приводили этот факт в подтверждение своей теории. В настоящее время этот вопрос приходится оставить в стороне, так как необычный экспонат давно уже утерян, хотя нет никакого сомнения в том, что он существовал.
Верандри, конечно, ничего не знал о теории татарского происхождения племени, но его открытие насторожило французские официальные круги, которые пришли к выводу, что должен существовать морской путь в Азию. Это убеждение было подкреплено сообщением Верандри о реке Миссури, которая, по его словам, текла на запад (позднее ему пришлось признать, что в том месте, где он ее видел, она течет на восток, но дальше она поворачивает на юг и оттуда направляется к Тихому океану). Из своей следующей экспедиции в 1738 году он вернулся с известием, полученным от индейцев Манитобы о существовании другой реки на западе. Один из индейцев сообщил ему, что плавал вниз по этой реке, и рассказал, что она ведет к такой стране, где климат теплый, где растут перец и какао и есть драгоценные металлы, «дикие звери всякого рода, змеи необыкновенных размеров» и «белые люди, окружившие стенами свои города и форты». Очевидно, какие-то сведения об испанских поселениях в Южной Америке просочились на север и дошли до этих индейцев.
Два человека, оставленные Верандри на реке Миссури, вернулись позднее с уже знакомой нам легендой индейцев об озере, воду которого нельзя пить. Следующую экспедицию удалось снарядить только в 1742 году, но ее участников испугали рассказы о враждебных племенах на западе, на той территории, которая отделяла их от моря. Они все же пересекли страну Бэд-Лендс и дошли до гор Блэк-Хиллс. Один из сыновей Верандри хотел было подняться на них в надежде увидеть долгожданное море, но осторожные проводники-индейцы, испытывавшие страх перед племенами этих мест, помешали ему это сделать.
