But, wouldn't it have been under ice 10,000 years ago? (The Gulf Stream wasn't flowing back then to keep it warm, right?)
The last big Ice Age 'melt-surge' occurred between 7-8,000 years ago.
According to the Center for the Study of the First Americans web site:
In the Last Glacial Maximum, at the time of the middle Solutrean period, a permanent ice rim connected the southwest coast of Ireland to the Grand Banks. In winter, the Atlantic froze as far south as the Bay of Biscay. The Gulf Current that today extends across the North Atlantic was shifted southward; it circulated clockwise, moving toward the Grand Banks and returned to the Bay of Biscay. Contrary to popular belief, the North Atlantic at this time was not unremittingly hostile. Short-term intervals and possibly longer periods of moderate weather would have enabled even inexperienced navigators to sail along the ice rim. Eventually hardy sailors would have traveled the short winter route to the Grand Banks, stupendously rich in fish and game. From there the leap to North America was assured.