Madeiraite was named after the Madeira island. It's the type-locality mineral for the Automous Region of Madeira.
The species was found by Pedro Alves in two gabbro outcrops near Porto da Cruz, Machico, northeast Madeira Island, Portugal. These small outcrops Terra do Batista and Serrado are intercepted by the Massapez and Volta streams, respectively, where the samples were collected. The set of rocks comprises gabbros, monzogabbros and essexites in contact with lithologies from the Porto da Cruz Unit - hyaloclastites, hyaloclastite breccias and submarine lava flows that belong to the CVI (lower volcanic complex) and date from the Miocene >5.57 My (Brum da Silveira et al., 2010).
Madeiraite occurs in the microcavities of the gabbros, associated with ilmenite, tungusite, aenigmatite and analcime. Other minerals which occur in the cavities include aegirine, augite, baddeleyite, britholite-(Ce), wöhlerite, catapleiite, calciocatapleiite, eudialyte and zirconolite.