1985 (júl/august)
Pedro Ayres Magalhães, basgitarista skupiny Heróis do Mar a Rodrigo Leão, basgitarista skupiny Sétima Legião, znudení svetom populárnej hudby, sa rozhodli, že skúsia hrať iný typ hudby. Vo voľnom čase medzi koncertmi svojich skupín sa stretávali a skúšali komponovať skladby pre dve klasické gitary. Onedlho sa k nim pridal Gabriel Gomes, akordeonista skupiny Sétima Legãio.
1986 (október)
Členom skupiny sa stal Francisco Ribeiro, Pedrov priateľ, ktorý študoval violončelo na Lisabonskom konzervatóriu, ale ešte stále im chýba hlas, keďže so žiadnou zo speváčok, ktoré si dovtedy vypočuli, neboli spokojní. Jeden večer navštívili Rodrigo Leão a Gabriel Gomes bar v štvrti Bairro Alto, kde ich zaujala mladá žena, ktorá zrazu začala spievať fado pri stole s priateľmi. Vtedy sa po prvý krát stretli s Teresou Salgueiro, v tej dobe ešte teenagerkou. Pozvali ju na skúšku, kde ju nechali spievať repertoár, ktorý dovtedy vytvorili. Po niekoľkých pesničkách si uvedomili, že to je hlas, ktorý hľadali. Prvé skúšky kompletnej skupiny sa uskutočnili v miestnosti, kde cvičili Heróis do Mar, neskôr začali cvičiť v Teatro Ibérico.
1987
Na jar skupina získala svoje meno, nahrala svoje prvé demonahrávky a Pedrovi sa podarilo presvedčiť hudobné vydavateľstvo EMI Valentim de Carvalho, ktoré predtým už vydalo platne Heróis do Mar a Sétima Legião, aby nahralo a vydalo aj ich prvú platňu. Nahrávanie platne sa uskutočnilo v júni v divadle Teatro Ibérico. 29. novembra v Porte a 30. novembra v Lisabone odohrala skupina svoje prvé verejné koncerty ako predkapela skupiny Sétima Legião. Začiatkom decembra vyšla ich prvá platňa Os Dias da Madredeus. Piesne sa hneď začali hrať v rádiách a v novinách sa objavili prvé recenzie, pričom Madredeus sú okamžite považovaní za významný medzník v portugalskej hudbe.
1988
Madredeus boli pozývaní na čoraz väčšie množstvo koncertov po celej krajine. Hrali v mestách ako Lisabon, Setúbal (koncert pod šírym nebom pred 8000 divákmi), Santa Maria da Feira, Barreiro, Reguengos, Viana do Castelo, Santa Maria (na Azoroch), Cova da Piedade, Angra do Heroísmo (znovu na Azoroch), Aveiro, Sines a Coimbra. V decembri sa ako reprezentanti Portugalska zúčastnili umeleckého festivalu v Bologni v Taliansku. Do konca roka ešte nakrútili svoj prvý videoklip k piesni Vaca do Fogo.
1989
Skupina bola čoraz žiadanejšia a odohrala množstvo koncertov po celom Portugalsku. V lete Madredeus absolvovali nezabudnuteľný koncert v kostole Igreja de Sao Luís dos Franceses, ktorý bol príliš malý na to, aby sa doňho zmestil veľký dav fanúšikov a tak veľká časť z nich počúvala na ulici cez otvorené dvere kostola. Od novembra hrala skupina na koncertoch nové skladby a pripravovala sa na nahrávanie novej platne. Skupina odišla z kláštora Convento de Madre de Deus a začala cvičiť v Colectividade de Santa Catarina, blízko hradu sv. Juraja, odkiaľ je krásny výhľad na rieku Tejo.
1990
Skupina nahrala platňu Existir medzi februárom a aprílom v štúdiách Namouche v Lisabone. Tam sa zoznámila s Antóniom Pinheirom da Silvom, bývalým členom významných portugalských skupín sedemdesiatych rokov Perspectiva a Banda do Casaco, ktorý sa nakoniec stal spoluproducentom platne a spolupracoval s Madredeus až do roku 1996. Dňa 19. a 20. apríla predstavili svoju novú platňu naživo v Tivoli Cinema. V máji navštívili Viedeň, kde hrali pred starostom hlavného mesta. Potom sa vrátili do Portugalska a koncertovali po celej krajine. V tomto roku po prvý krát navštívili Macao. Ich debutová nahrávka vyšla na CD, pričom bola vynechaná pieseň Cantiga do Campo, ktorá sa dodnes nachádza len na pôvodnej vinylovej verzii.
1991
Na začiatku roka Madredeus pokračovali v koncertnom turné Existir po Portugalsku. V marci nahrali videoklipy k piesňam Cuidado a O Pastor. Na začiatku apríla hrali vo Florencii, kde sa uskutočnil Portugalský kultúrny týždeň. Potom sa vrátili na Azorské ostrovy a odtiaľ odleteli do Barcelony na svoj prvý koncert v Španielsku. Dňa 30. apríla v Coliseu dos Recreios v Lisabone Madredeus odohrali koncert, na ktorom vystúpili ako hostia Carlos Paredes, klasik portugalskej gitary, gitaristka Luisa Amaro a 80 členný spevácky zbor. Koncert bola nahrávaný a vyšiel ako dvojalbum Lisboa. Po tomto skupina pokračovala v turné po Portugalsku a po prvý krát vystúpila v Rio de Janeiro. Na konci roka Madredeus vystúpili po prvý krát aj v Belgicku.
1992
V tomto roku Madredeus takmer vôbec nekoncertovali v Portugalsku, odohrali len päť koncertov v Lisabone. Väčšinu roka strávila skupina na koncertoch v zahraničí – v Belgicku, Francúzsku, Španielsku, Japonsku a Holandsku. Pred Vianocami vyšiel ich živý dvojalbum Lisboa.
1993
Na začiatku roka sa ukázalo, že počet koncertov naplánovaných na tento rok enormne vzrástol. Skupina hrala v Nemecku, Belgicku a Španielsku. Pedro Ayres Magalhães sa venoval aj iným projektom (skupina Resistência) a pre nedostatok času pozval gitaristu José Peixota, aby zaňho hral pri živých vystúpeniach Madredeus. Pedro Ayres sa veľmi rýchlo vrátil, ale José Peixoto už v skupine zostal a z Madredeus sa stal sextet s dvoma gitaristami. V júni hrala skupina na festivale Portugal ao Vivo na štadióne v Lisabone, pred 50 000 divákmi. V lete nahrala ďalší videoklip k piesni O Pastor. V lete odohrali aj niekoľko koncertov v Grécku, nasledovalo Holandsko a nezabudnuteľné turné v Japonsku.
1994
Po dvoch týždňoch odpočinku na začiatku roku sa členovia skupiny znovu zišli (tentoraz v dome Gabriela Gomesa) a začali pracovať na nových piesňach. Počas tohto obdobia nahrali verziu skladby Maio, Maduro Maio, ktorá sa objavila na platni Filhos da Madrugada venovanej José Afonsovi. Za Pedrom Ayresom Magalhaesom prišiel Wim Wenders, ktorý sa chystal nakrútiť film o Lisabone a chcel v ňom použiť nejaké pesničky Madredeus. V marci skupina odletela do Londýna spolu s Antóniom Pinheirom da Silvom a Jonathanom Millerom (britským zvukárom, ktorý žil v Lisabone), aby nahrala svoju novú platňu. Dňa 5. mája skončili nahrávanie i mixovanie, ale na veľké prekvapenie nahrávacej spoločnosti nahrali hneď dve platne. Prvou platňou bola Espírito da Paz, ktorá vyšla ešte v tú jar. Druhou, nečakanou platňou, bola Ainda, soundtrack filmu Wima Wendersa, ktorý sa ešte ani nezačal nakrúcať. Počas krátkej návštevy Portugalska skupina nakrútila videoklipy k skladbám Vem a Ao Longe o Mar a svoj part vo filme Wima Wendersa. Nové pesničky boli predstavené verejnosti na nezabudnuteľnom koncerte v kláštore v Batalhe a potom v Aveiru, Brage, Brazílii, Kodani a Bruseli. Na začiatku júla hrali Madredeus na koncertoch v Lisabone a Porte venovaných José Afonsovi. Vtedy Rodrigo Leão oznámil svoje rozhodnutie opustiť skupinu, pretože už nedokázal držať krok s intenzívnym pracovným tempom kapely a chcel sa venovať aj sólovej hudobnej kariére. V skupine ho nahradil Carlos Maria Trindade, Pedrov spoluhráč z Heróis do Mar. Týždeň pred Vianocami boli všetky platne Madredeus v Top 20 Portugalskej gramofónovej asociácie, čo sa dovtedy nepodarilo nikomu v histórii portugalského hudobného priemyslu.
1995
V januári prerušil krátke prázdniny skupiny Wim Wenders, ktorý prišiel do Lisabonu, aby nakrútil videoklipy k pesničkám Céu da Mouraria a Alfama. V marci kapele vyšla platňa Ainda, uskutočnila sa premiéra filmu Wima Wendersa Lisabonský príbeh a skupina odohrala 19 koncertov v Portugalsku. V apríli odcestovali na Azorské ostrovy, kde nakrúcal dokumentárny film o skupine, ktorý režíroval Holanďan Rob Rombout. Do Portugalska sa vrátili koncom júla a počas augusta odohrali sériu open-air koncertov na historických miestach Portugalska. Začali na hradbách Vila Nova de Cerveira a potom pokračovali na námestí Praça João Franco v Guimarães, v kláštore São Bento da Vitória v Porte, v záhradách paláca Queluz, v Solar de Mateus pri Vila Real a v starej jazdeckej aréne v pevnosti Almeida. V septembri odohrali koncert v São Paulo s orchestrom, ktorý dirigoval Jaques Morelenbaum (spolupracoval napr. s Caetanom Velosom alebo portugalskou speváčkou Dulce Pontes) a po prvý krát vystúpili v USA v New Yorku, Bostone, San Franciscu a Los Angeles. V novembri odohrali v Lisabone koncert pri príležitosti vydania knihy Jorge P. Piresa Um Futuro Maior, ktorá je spojená s históriou skupiny.
1996
Členovia skupiny sa znovu zišli začiatkom januára, aby prerokovali svoju zmluvu s nahrávacou spoločnosťou. Rozhovory trvali dva mesiace. V tomto období sa na členoch skupiny začala prejavovať nahromadená únava z dlhoročného a neustáleho koncertovania a vzťahy v skupine začali byť trochu napäté. Až do konca roku sa nič nedialo.
1997
Všetky plánované aktivity na rok 1997 boli zrušené. Vo februári začali v Belémskom kultúrnom centre nacvičovať Pedro Ayres Magalhães, Teresa Salgueiro, José Peixoto a Carlos Maria Trindade. Dňa 6. júna bola podpísaná zmluva, v ktorej Gabriel Gomes a Francisco Ribeiro potvrdili svoj odchod zo skupiny. O týždeň na to bol pozvaný do kapely basgitarista Fernando Júdice, bývalý člen skupiny Trovante a Pedrov spoluhráč zo skupiny Resistência. Začiatkom júla neformálne predstavili novinárom nové zloženie skupiny a nový repertoár. Koncom júla odcestovali do Talianska kde v nahrávacích štúdiách Condulmer v Zobran di Mogliano blízko Benátok nahrali novú platňu O Paraíso. Nové piesne boli po prvý krát predstavené portugalskej verejnosti 18. septembra na koncerte pri ruinách Dianinho chrámu v Évore.
1998 – 2004
V roku 1998 vyšiel dvojalbum Porto s nahrávkou koncertu v Coliseu v Porte. V októbri sa Terese narodila dcéra Inês, takže v nasledujúcich mesiacoch skupina zvoľnila pracovné tempo. V roku 2000 vyšla platňa Antologia s výberom skladieb z predchádzajúcich štúdiových nahrávok. Na albume sú aj dve nové skladby, jedna z nich, Brumas do Futuro, sa objavila vo filme Capitães de Abril (Apríloví kapitáni), ktorý režírovala Maria de Medeiros. V roku 2001 vyšla platňa Movimento. V roku 2002 si Pedro Ayres splnil svoj dávny sen – hrať skladby Madredeus s veľkým orchestrom. Party pre orchester napísal známy portugalský hudobný skladateľ António Vitorino d’Almeida. Väčšinou ide o skladby z platne Movimento. Nahrávka z koncertu v Brugách v apríli roku 2002, na ktorom vystúpili Madredeus spolu s Orchestrom flámskeho rozhlasu, vyšla na jeseň roku 2002 ako dvojalbum Euforia. V roku 2002 vyšla aj platňa Electronico s remixami slávnych skladieb. V roku 2003 Madredeus hlavne koncertovali, hrali aj blízko Slovenska, v Budapešti na festivale Sziget a v Katowiciach. Na rok 2004 si členovia skupiny chceli oddýchnuť a venovať sa príprave novej platne, ktorá vyšla v tom istom roku pod názvom Um Amor Infinito.
2005
Vo februári vyšla ďalšia nová platňa Faluas do Tejo, ktorú nahrali spolu s platňou Um Amor Infinito, podobne ako kedysi naraz nahrali platne O Espírito da Paz a Ainda. Táto platňa je tematicky venovaná mestu Lisabon. V júni odohrala skupina dva koncerty veľmi blízko Slovenska – v Budapešti.
2006 – 2007
V nasledujúcich dvoch rokoch sa skupina dať si oddych, aby sa jej členovia mohli venovať svojím paralelným projektom. Teresa Salgueiro v roku 2007 vydala dva albumy – Você e Eu a La Serena v spolupráci s Lusitânia Ensemble, ktoré produkoval Pedro Ayres Magalhães. Dvojica José Peixoto a Fernando Júdice založila skupinu Sal so speváčkou Anou Sofiou Varela. Fanúšikovia sa však neobávali rozpadu skupiny Madredeus, keďže súbežné projekty hudobníkov neboli pre nich ničím novým. Carlos Maria Trindade, Pedro Ayres Magalhães, José Peixoto a Fernando Júdice pracovali ako hudobní producenti, Trinidade a Peixoto viedli tiež celkom úspešnú sólovú kariéru. Aj preto ohlásenie odchodu Teresy Salgueiro, Fernanda Júdice a Josého Peixota 28. novembra 2007 fanúšikov prekvapilo. Pedro Ayres Magalhães vyhlásil, že budúcnosť skupiny je neistá, keďže je ťažké predstaviť si návrat bez Teresy Salgueiro a jej symbolického hlasu.
2008 – 2010 Madredeus & A Banda Cósmica
V roku 2008 však Madredeus predsa len vydali album Metafonia. Po odchode Teresy Salgueiro, Fernanda Júdice e Josého Peixoto sa Pedro Ayres Magalhães a Carlos Maria Trindade rozhodli nenahradiť ich novými hudobníkmi, ale vytvoriť si vlastné ensamble, ktoré nazvali A Banda Cósmica. Tvorili ho speváčky Rita Damásio a Marina Abrunheiro, na harfe hrala Ana Isabel Dias, na perkusiách Ruca Rebordão, na elektrickej gitare Sérgio Zurawski, na base a kontrabase Gustavo Roriz, na bicích Babi Bergamini a na husliach dočasne pozvaný umelec Jorge Varrecoso (neskôr ho nahradil António Barbosa ako trvalý člen kapely). Skupina v tomto zložení vydala v roku 2009 svoj druhý album A Nova Aurora. O rok nato vyšla tretia a posledná štúdiová nahrávka Castelos na Areia, čím zoskupenie Madredeus & A Banda Cósmica ukončilo svoju spoluprácu.
2011 – 2012
V roku 2011 skupina ohlásila návrat v staronovej zostave Pedro Ayres Magalhães (klasická gitara) a Carlos Maria Trindade (klávesy), Jorge Varrecoso (husle), António Figueiredo (husle), Luís Clode (violončelo) a Beatriz Nunes (spev). Dňa 2. apríla 2012 vyšla doska Essência, ktorou chcela kapela osláviť 25 rokov svojej existencie.