The French claim to North America was based on the right of discovery, a European concept that allowed France to assert legal ownership of lands not occupied by Christians. New France "was first discovered by French Bretons, in the year 1504," 1 followed by Jacques Cartier's voyages to the St. Lawrence River.
The French king, Francis I, financed explorations by Giovanni Verrazano to explore the coast of North America in 1524. Verrazano chose to stay rather far from the shore, missing the mouth of Chesapeake Bay and Delaware Bay but discovering New York harbor, where a bridge bears his name. Verrazano did stop at what may have been Hatteras. There, he had the political good sense to name the land "Francesca." He may have seen Albemarle/Pamlico Sound behind the barrier islands, but he wrote that he saw the Pacific Ocean:
The first French attempts to colonize the New World were in the St. Lawrence Valley in the 1540's, then in Brazil at Guanabara Bay (now Rio De Janiero) in 1555.
Jean Ribault led a French attempt to establish a permanent colony in 1562 in what is now South Carolina. He left 27 settlers at Charlesfort, near the current Marine Corps Recruit Depot at Parris Island. However, Ribault's plans for a quick return to France and re-supply of the colony were blocked by Catholic/Protestant warfare. He was a Huguenot (French Protestant), and he finally sought assistance from a fellow Protestant - Queen Elizabeth.
While some of the earliest French settlement efforts failed, the French did establish settlements in North America before the English succeeded in creating a permanent settlement at Jamestown in 1607. The French government succeeded in establishing colonies in Canada and Louisiana, on either side of the area where the English ended up focusing their efforts (between the Chesapeake Bay and Georgia). French-speaking Quebec and the Napoleonic legal code of Louisiana are two modern indicators of the French government's colonial successes in creating New France in the New World.
Long before the English arived in Virginia, the Spanish had founded the oldest permanent European settlement in North America - St. Augustine, Florida - in 1565. Jamestown was not even the second permanent European settlement in North America. The first winter of the English at Jamestown in 1607-08 was the fourth winter for the French in New England, starting at St. Croix in Maine in 1604 and moving to Acadia in Nova Scotia in 1605.
Just one year after Jamestown, in 1608, Samuel de Champlain founded Quebec. In 1613, Father Pierre Biard led three other Jesuit priests and about 40 other Frenchmen to establish a settlement at Mount Desert Island (now in Southwest Harbor at Acadia National Park).
Unfortunately for the French, an English ship under Captain Samuel Argall arrived unexpectedly in 1613 (perhaps after being blown off course by a storm) at Mount Desert Island. The English captured the settlement, in part because one-third of the French were on another ship exploring the region.
Argall knew the settlement was authorized by a commission from the French king, but he secretly removed it from the French ship and claimed that he was dealing with "pirates." Half of the Frenchmen were given a small ship and allowed to sail away, since the English lacked the room to transport them all to Jamestown. (The Jesuits assumed summary execution of the "heretics" was avoided because the English thought the missing French colonists may have been watching.)
The Jesuits were not tried and executed in Jamestown either, in part because Argall revealed the existence of the French king's commission. The priests were carried back to their settlement by Argall on an expedition to find and destroy the nearby settlements at Sainte Croix and Port Royal - and perhaps offload the priests onto French fishing boats for a ride home to Europe. The English destroyed the French buildings, but a storm blew their ship far away from the coast. Argall had to sail with the Jesuits to the Azores, and from there he went to England. The Jesuits were returned safely to France, in the end.
It took about 150 years after Columbus discovered the New World for the international rivalry between France and England to reach Virginia. When the French actually threatened the English colony in the mid-1700's, the danger came from the Ohio River rather than from the Atlantic Ocean during the French and Indian War.
References
1 Thwaites, Reuben Gold, The Jesuit Relations and Allied Documents: Travels and Explorations of the Jesuit Missionaries in New France, 1610-1791 - Vol. III Acadia, 1611-1616, online at http://puffin.creighton.edu/jesuit/relations/relations_03.html