There's good evidence that "Europeans" were crossing the Atlantic as far back as 9000 years ago. In fact, there's good evidence that the New World has been "discovered" many times. Had Columbus not completed his voyages, very shortly thereafter either England, France, Portugal, or Spain would have had another sailor be the "first", as those nations had reached the technological stage to travel back and forth across the ocean.
This old poem illustrates that many others have been to the New World before Chris: (Enjoy!)
A MISLAID CONTINENT (from Whiffs from Wild Meadows, Sam Walter Foss, circa 1880)
Now let us run the list over, Of men preceding Christopher, Who came before Columbus came, that laggard dull and slow ; The early Buddhist missionaries, Those rapt religious visionaries, Who thirteen hundred years ago discovered Mexico. An Irishman named Brendin (The list is never ending) He crossed the Sea of Darkness, crossed the wild, untravelled main. He thought that he would try a land Some miles away from Ireland; So he, twelve hundred years ago, discovered us again. Leif Ericson, the Norseman, A regular old sea-horseman, Who rode the waves like stallions, and couldn t endure the shore, Five hundred years thereafter Said to his wife in laughter, " It s time to go and find, my dear, America once more." And so he went and found it, With the ocean all around it, And just where Brendin left it five hundred years before ; And then he cried, " Eureka ! I m a most successful seeker!" And then went off and lost it, could not find it any more. They fought the sea, and crossed it, And found a world and lost it ; Those pre-Columbian voyagers were absent-minded men. Their minds were so preoccupied, That when a continent they espied, They absently mislaid it, and it couldn t be found again. But Columbus when he found us Somehow kept his arm around us, For he knew he must be careful when he found a hemisphere ; And he knew just how to use it, And he didn t misplace and lose it, And mislay it in a corner where it couldn t be found next year. Like a pretty worthless locket He didn t put it in his pocket, And drop the New World through a hole that he d forgot to mend ; But he kept his eye upon it, And he kept his finger on it, And he kept his grip upon it, and held on it to the end.
Assuming that Christopher Columbus had not been successful in reaching the New World in October 1492, it is reasonable to suggest that Spain, along with Portugal the most powerful naval nation in the world during the sixteenth century, would have discovered the New World by 1600.
First of all, remember that Christopher Columbus was not even seeking the New World; instead, he hoped to find a westward route to the Indies. Whether Columbus had been successful or not would have done little to diminish European interest in a westward route. The eastern land route, as well as the sea route around Cape Horn, was both treacherous and fraught with danger. This being said, uncertainty concerning the breadth of the Atlantic Ocean would have slowed pursuit of such a route. With continued eastward trade and more and more detailed mapmaking, cartographers and mathematicians could approach more and more accurate estimations of the earth’s size, as well as that of the Atlantic Ocean. With more dependable calculations, it would seem reasonable to assume that explorers/adventurers, operating under the same assumption as Columbus, would have begun to take chances to find a westward route to the east.