Vines were brought to the island by the first colonizing party, the Portuguese, in the late 15th century, and wine has been made ever since. But, as the story goes, one barrel shipped to the New World accidentally remained on board and sailed back to Madeira. The captain assumed that the wine was now bad, having sat in the barrel on his boat for so long. But upon tasting, it had improved!
It turns out that the slow heating in oak barrels, which happened naturally during the sea voyage, and now happens naturally in oak barrels stowed in the attics of wineries (or in the cheaper varieties, in heated vats), was responsible for the special flavor.
We toured the Blandy's winery in downtown Funchal, one of the oldest and biggest, run by the Blandy family of Britain. They had a great tour including a wine-tasting.
But for a more interesting experience we went to a little place, barely marked, off one of the side streets... the home and winery of the Barros e Sousas brothers. Mr. Barros e Sousas was effusively welcoming, insisting that we climb up to his attic to see all the dusty barrels, that we taste some bottles, etc. Neat place! Most of his father's and grandfather's barrels had worn so much that the writing was not always legible, and thus many old old barrels are of uncertain vintage. Thus he sells them as "extra reserve" (from his grandfather's day) or "reserve" (from his father's day) since he is not allowed to cite them as a specific vintage. They thus cost less... but taste great!