In September 1522, the surviving members of Ferdinand Magellan's crew returned to Spain, having circumnavigated the globe. Competition in trade was becoming urgent, especially with Portugal. King Francis I of France was impelled by French merchants and financiers from Lyon and Rouen who were seeking new trade routes and so he asked Verrazzano in 1523 to make plans to explore on France's behalf an area between Florida and Terranova, the "New Found Land", with the goal of finding a sea route to the Pacific Ocean.

Within months, he sailed neared the area of Cape Fear on about March 21st and, after a short stay, reached the Pamlico Sound lagoon of modern North Carolina. In a letter to Francis I described by historians as the Cèllere Codex, Verrazzano wrote that he was convinced that the Sound was the beginning of the Pacific Ocean from which access could be gained to China.

Continuing to explore the coast further northwards, Verrazzano and his crew came into contact with Native Americans living on the coast. However, he did not notice the entrances to Chesapeake Bay or the mouth of the Delaware River. In New York Bay, he encountered the Lenape in about 30 Lenape canoes and observed what he deemed to be a large lake, really the entrance to the Hudson River. He then sailed along Long Island and entered Narragansett Bay, where he received a delegation of Wampanoag and Narragansett people.

He discovered Cape Cod Bay, his claim being proved by a map of 1529 that clearly outlined Cape Cod. He named the cape after an important French ambassador in Rome, and called it Pallavicino. He then followed the coast up to modern Maine, southeastern Nova Scotia, and Newfoundland, and he then returned to France by 8 July 1524. Verrazzano named the region that he explored Francesca in honor of the French king, but his brother's map labeled it Nova Gallia (New France).