Some medieval records indicate weather (drought years, particularly bad storms, et cetera), but they didn't have the organizational longevity (or the interest) to record long-term climate trends. Besides tree rings and ice cores, is there any "anecdotal" evidence from the Middle Ages itself that suggests long-term changes in average temperature?
|Erik the Red|
Let us look at Erik Thorvaldsson (950-c.1003), aka Erik the Red. Erik's father wasn't the most easygoing guy, and was exiled from Norway, whereupon he took his family to Iceland. Around 982, Erik himself got into trouble for killing some people (poor anger management was apparently a family issue). He sailed from Iceland to Greenland, where legend says he created the first settlement. It is likely that there was already a Norse presence, but Erik can probably claim credit for the first permanent habitation.
If we can believe the sagas and records, then even though life was very harsh, in the 1120s there were sustainable settlements on the eastern shore that held 2000-4000 people. One modern scholar reports "190 small farms, 12 parish churches, a cathedral, an Augustinian monastery, and a Benedictine nunnery." On the western shore were "90 farms and four churches."
Why the Norse settlements ultimately failed is a target for speculation–one theory is that rising amounts of sea ice made navigation, and therefore trade that was necessary to keep their society going, difficult–but here's the thing: excavations of those early settlements have found quite a bit of evidence of their way of life—but they have to dig under "permanently" frozen ground to do so.
It is clear that those settlements existed—could only exist—at a time that was significantly warmer than Greenland's climate is today.