Yeah, it's my personal beleif that Vikings were probably the first europeans to make it across, at least by the evidence that we have.
A funny side note: An amateur Nova Scotian historian named Paul Chiasson has claimed to have found a Chinese settlement on Cape Breton Island (the northern section of NS), dating back to the 1300s. Apparently, the road width and structure platform measurements are consistent with ancient settlements in China, and some stone platforms that resemble those found in the Forbidden Palace. He contends that an large armada of chinese ships sailed through the indian ocean, past the atlantic, and decided to set up an outpost on the eastern side of the windy little island. Local historians have largely dismissed his claims, claiming that the site is probably an abondonned loyalist farm, and Chiasson has refused to release the location until it is designated a protected provincial historical site. Provincial officials and member of the Nova Scotia Musem have declined offers to visit the site. This hasn't deterred Chiasson, however, who stated in a press conference:
"I understand the reticence on the part of the government and the museum because it is world changing and they missed it....t's either a grand hoax or a great discovery because it's nothing in between"
The last word I have heardon the matter is that Mr Chiasson has teamed up with Gavin Menzies (1421: The Year China Discovered America) to write a book on the topic. I'm very interested to see what he has for evidence..!