Madeira Re-discovered

Madeira appears on maps as early as 1339. From a portolan dating to 1351, and preserved in Florence, Italy, it would appear that the islands of Madeira had been discovered long before Portuguese vessels rediscovered them in the "official" timeline. In Libro del Conocimiento (1348–1349), a Spanish monk also identified the location of the islands in its present location, with the names Leiname, Diserta and Puerto Santo. Officially, in 1418, two captains under service to Prince Henry the Navigator, João Gonçalves Zarco and Tristão Vaz Teixeira, were driven off-course by a storm to an island which they named Porto Santo (English: holy harbour); the name was bestowed for their gratitude and divine deliverance from a possible shipwreck by the protected anchorage. 

The following year, an organized expedition, under the captaincy of Zarco and Vaz Teixeira, was sent to this new land, and along with captain Bartolomeu Perestrello, to take possession of the island on behalf of the Portuguese crown. Consequently, the new settlers discovered "a heavy black cloud suspended to the southwest", which when explored they discovered the larger island of Madeira.