Olyckan inträffade i en kurva i kuststaden Caniço omkring 18.30 lokal tid. Bussen ska då ha kört av vägen och vält nedför en slänt och landat ovanpå ett hus, skriver nyhetssajten Diário de Notícias.
Antal döda uppges vara minst 29 personer och merparten ska vara tyska medborgare, rapporterar Reuters.
Portugals president Marcelo Rebelo de Sousa, flög under kvällen till Madeira för att visa sitt stöd till de drabbade.
– Jag uttrycker sorgen och solidariteten från alla portugiser i den här tragiska stunden. Framförallt till offrens familjer, som jag har fått berättat för mig att alla var tyskar, sa han ett tv-sänt tal.
”Jag saknar ord”
Även borgmästaren i Caniço uttryckte sin sorg.
– Jag saknar ord för att beskriva vad som har hänt. Jag har svårt att hantera det lidande som människorna har utsatts för, sa Filipe Sousa till lokala medier.
Ombord på bussen fanns drygt 50 personer, där de flesta var turister i åldrarna 40 till 50 år berättar räddningstjänsten för Reuters.
Bland de avlidna var 18 kvinnor och 11 män och många av dem var pensionärer, skriver Reuters med hänvisning till tyska medier.
20-tal vårdas på sjukhus
Utöver dödsoffren skadades över 20 personer i olyckan som fördes till ett sjukhus i staden Funchal. Merparten är tyskar men även personer från Madeira finns bland de skadade. En talesperson för sjukhuset, Dr. Nélio Mendonça, bekräftar för tyska Bild att många är svårt skadade.
– Vi har för närvarande våra händer fulla. Vi har många skadade personer från bussolyckan här. Ambulanserna körde dem från Santa Cruz till oss.
Bussens chaufför och turistguiden uppges ha skadats i samband med kraschen men överlevt, skriver TT.
UD undersöker olyckan
Premiärministern Antonio Costa skickade en beklagande hälsning till Tysklands förbundskansler Angela Merkel.
”Till alla involverade familjer skickar jag mina djupaste kondoleanser”. Skrev han på Twitter.
Svenska UD hade på onsdagskvällen inga uppgifter om att några svenskar ska vara inblandade i olyckan.
– Vi undersöker det vidare via vår ambassad i Lissabon, säger Lina Eidmark vid UD:s presstjänst.