Yes:
The islands started to be settled circa 1420 or 1425. In 23 September 1433, the name Ilha da Madeira (Madeira Island or "wood island") appears on a map, its first mention in a document.
I've tried putting Azores, Madeira and surrounding seas as terra incognita for Portugal (Watk 3.11) and gave Portuguese an explorer. Both were colonized to a city without a problem by 1425 with appriopriate AI file.