Of course it was "new" only to the inhabitants of Europe, Asia, and Africa. Humans evolved into a unique species in Africa from Australopithecus 5 million years ago, through Homo habilis to Homo erectus to Homo sapiens (with many dead ends, including Homo neanderthalensis) before our current species established itself 500,000 years ago. Homo sapiens, in multiple journeys, migrated into North America perhaps 50,000 years ago. What became Virginia had been occupied by humans for roughly 15,000 years, according to the archeological evidence.
In those 15,000 years, sailing expertise had developed in many places. In recorded history, we know the most about the skills in Mediterranean and on the Chinese coast, but it's clear that the Scandinavians were also capable of long-distance journeys to Greenland and Newfoundland.
On the eastern coastline of North America, however, the natives were able to travel in dugout canoes across the Chesapeake Bay. Some "Americans" reached the islands of the Caribbean, the Bahamas, and Bermuda, but ocean travel was essentially unknown to the first residents of Virginia until the Spanish arrived.
In Asia, the Chinese under the Ming Dynasty abandoned the explorations of Zheng He (Cheng Ho) after seven voyages, 75 years before Columbus reached America. The Chinese and the westerners had equivalent technology in the 1400's, but the nation states of Europe competed through exploration and trade while the centralized government and economy of China chose to conserve its culture and limit exposure to other sofcieties.
In Europe, the sailing skills in the Mediterranean in Italy, Greece, Turkey, and North Africa were overcome by the oceanic sailing expertise of the nation states on the Atlantic Ocean. The Dutch focused on Asia rather than North America, while Portugal, Spain, England, and France soughht weath and power through colonies in the New World.