They officially became the first men to set foot on the heavily forested island, naming it Ilha da Madeira,  Island of Timber.  
They landed on the Island of Timber, the first men to ever do so.
They didn't land on the Island of Timber, the first men to ever do so.