Исследователи не могут прийти к единому мнению относительно немногих и весьма путаных сведений о первом этапе плавания Веррадзано. Известно, что флорентийский мореплаватель вышел из Дьепа с четырьмя кораблями, зафрахтованными королевским домом, осенью 1523 года. Между там дальнейший переход через Атлантику он совершал на единственном корабле. Наиболее правдоподобное объяснение состоит в том, что два корабля предназначались для пиратских нападений на испанских торговцев, а еще один корабль погиб во время бури. Опытный моряк, Вер-радзано бывал в Португалии и ее колониях в Мозамбике и состоял в хороших отношениях с португальским адмиралтейством, что позволило ему получить разрешение на промежуточную остановку на Мадейре. Как уже говорилось, этот остров для португальского королевства завоевал свекр Колумба, а сам генуэзский мореплаватель нашел там чрезвычайно ценную для своих экспедиций информацию.

Колумб был родом из Генуи и поэтому был хорошо принят генуэзской общиной Мадейры. Но в ту эпоху еще не существовало единой Италии, и генуэзцы, хотя и понимали язык, на котором говорил Веррадзано, считали его иностранцем, который к тому же плавал под французским флагом. Поэтому маловероятно, чтобы флорентиец был радушно встречен богатой генуэзской буржуазией острова, но вполне возможно, что он был связан с Рыцарями Христа, то есть с местными тамплиерами, потомками Синклера. В любом случае, в своем докладе Франциску I Веррадзано сообщает, что он задержался на «необитаемом островке», которым мог быть маленький и практически безлюдный остров Порто-Санто, состоявший под управлением связанной с тамплиерами семьи Фелипы де Полестрельо, португальской жены Колумба.

Джованни да Веррадзано покинул Мадейру 17 января 1524 года на борту своего единственного корабля, носившего название «Дофин», в честь французского наследника престола. Его сопровождал его брат Джироламо, исполнявший обязанности картографа, а команда состояла из 50 человек, с запасом провизии на восемь месяцев плавания. «Дофин» взял курс на запад, и через 40 дней плавания Веррадзано заметил берега современной Северной Каролины, рядом с мысом Гаттерас, но вынужден был отклониться на север, поскольку ему преградила путь испанская эскадра. Путешественник давал флорентийские названия «Аннун-циата», «Франческа» и даже «Веррадзания» деталям ландшафта, которые наносил на карту его брат. Затем он переводил их на французский в путевом дневнике, который вел для французского короля. Ни один из этих топонимов не сохранился до настоящего времени, но предполагается, что все обозначаемые ими местности находились между заливом Памлико и бухтой Делавар.

«Дофин» продолжал двигаться на север, пока не вошел в бухту современного Нью-Йорка, и тем же самым курсом добрался до острова Манхэттен, расположенного в проливе, который сегодня носит имя Веррадзано. Разведчик назвал бухту Святой Маргаритой, в честь сестры Франциска I, графини Алансонской. Он продолжил свой путь вдоль берега до Лонг-Айленда и исследовал еще один большой остров, который назвал Родос в честь местности, где разворачивается действие его любимой поэмы Саннадзаро. Сегодня вся эта территория относится к штату Род-Айленд, название которого и обозначет дословно «остров Родос». Там он вступил в контакт с вампаноагами, одним из алгонкинских племен. Если верить его дневнику, туземцы не удивились, увидев их, и некоторые из них, казалось, в покрое своих нарядов из шкур и перьев пытались подражать европейцам. Веррадзано пишет, что в этом сообществе были распространены целомудрие и моногамия, так же, как забота о слабейших членах племени. Именно вампаноаги сообщили мореплавателю, что на берегу бухты, которая сегодня носит название Ньюпорт, возвышается «священная постройка».

Моряк отправился в это место и к собственной радости, к которой примешивалось некоторое удивление, увидел на берегу баптистерий в тамплиерском стиле. Он запомнил его местоположение и другие подробности, а Джироламо нанес его на карту и зарисовал его. Несмотря на то что для его строительства были использованы местные материалы, его форма и размеры в точности повторяли подобные цистер-цианские и тамплиерские сооружения, возводившиеся в Европе в эпоху раннего Средневековья. Местность была пустынной, лишенной следов человеческого пребывания и давно заброшенной. На карте Веррадзано это место обозначено как «Вилья Норманда», что приоткрывает ее тайну, но не сообщает профанам истинный характер и значение постройки.

Экспедиция отправилась в дальнейший путь к Новой Земле, а оттуда вернулась в Дьеп, куда она прибыла в начале июля того же самого 1524 года. Великий успех тайной миссии Веррадзано внешне выгдядел как полный провал. Он не обнаружил ожидаемого прохода в Тихий океан, и, возможно, даже не искал его. Открытые им новые девственные территории не интересовали Франциска I, занятого трудной войной с империей, которая закончилась тем, что в битве при Павии французский монарх был взят в плен. Что касается точной карты берегов Атлантического океана, она абсолютно не требовалась покровителям Веррадзано, которые занимались торговлей шелком с Востоком.