Madeline Peyroux 16 évesen Párizs utcáin kezdte énekesi karrierjét álmodozó utcai zenészként, és leginkább ehhez a korszakhoz nyúl vissza a “Careless Love Forever” című európai turnéján.
Edith Piaf énekesnőhöz hasonlóan Madeleine Peyroux is tizenéves korában Párizs forgalmas utcáin zenélt. A “kis verébhez” hasonlóan Madeleine is összebarátkozott a város utcazenészeivel, és a latin negyedet választotta első fellépései színpadává. Évekkel később Peyroux Piaf-ot említette, mint aki a zenéjére legnagyobb hatással volt, rögzített is egy feldolgozást a La Vie En Rose című klasszikusból.
A kíváncsi tinédzser lógni kezdett az iskolából, hogy Párizs latin negyedébe járjon, ahol utcazenészek éltek, és meg akarta ismerni a zenéjüket és az életmódjukat. A rettenthetetlen tinédzser 16 évesen csatlakozott a Lost Wandering Blues and Jazz Bandhez, amellyel bejárta Európa utcáit, felfedezte Bessie Smith és Billie Holiday zenéjét, miközben “mohón összeszedett minden dalt és minden gitárjátékot”, amit csak tudott.
A kétéves turné-kaland Madeleine Peyroux-t egy életre kreatív útra terelte. 1991-ben a zenekar New Yorkba utazott, ahol Madeleine egyedülálló tehetségére felfigyelt Yves Beauvais, az Atlantic Records munkatársa. A fiatal énekesnő visszautasította a zenei vezető első lemezszerződési ajánlatát, de néhány évvel később engedett, és 1996-ban megjelent az áttörést jelentő Dreamland című albuma.