Madeleine Peyroux was born on April 18, 1974, in Athens, Georgia, and grew up in New York and California before her parents divorced and she moved with her mother to Paris in her early teens. Two years later she began singing with street musicians in the Latin Quarter, first with a vintage jazz group called the Riverboat Shufflers and then with The Lost & Wandering Blues and Jazz Band, a washtub bass, trumpet and guitar outfit with which she toured Europe. The band's independently issued CD Spreading Rhythm Around dates from 1997.

An Atlantic Records A&R executive, Yves Beauvais, signed her after hearing her sing, and her debut Dreamland appeared on October 1, 1996. Beauvais and the bassist Greg Cohen are credited as its producers, and the sessions in New York paired her with an unusually deep jazz and downtown band: Marc Ribot on guitar and dobro, James Carter on tenor saxophone and bass clarinet, Cyrus Chestnut on piano, Leon Parker on drums, Regina Carter on violin and Vernon Reid on one track. The repertoire ran from Bessie Smith's "Reckless Blues" and Edith Piaf's "La Vie en Rose" to "Walkin' After Midnight" and songs of her own, including "Dreamland" and "Always a Use." The album entered Billboard's Heatseekers chart at No. 36 in February 1997 and had sold about 200,000 copies worldwide by January 2005.

A gap of eight years followed before her next full-length record. Accounts of the period describe a stretch away from the public eye and vocal problems that included a cyst on the vocal cords requiring surgery. She came back on Rounder Records with Careless Love, released on September 14, 2004, and produced by Larry Klein, whose earlier work included records with Joni Mitchell and Shawn Colvin. Recorded in Los Angeles with the guitarist Dean Parks, keyboardist Larry Goldings, bassist David Piltch and drummer Jay Bellerose, it mixed Hank Williams, W. C. Handy, Bob Dylan, Elliott Smith and Leonard Cohen with one new song, "Don't Wait Too Long," which she wrote with Klein and Jesse Harris. It reached No. 7 on the UK albums chart and No. 2 on Billboard's Top Jazz Albums chart, and sold more than 500,000 copies in the United States. The same year she appeared on Got You on My Mind, a collection of songs with the guitarist William Galison on his Waking Up label. In 2021 Craft Recordings issued a deluxe Careless Love with a second disc from a July 15, 2005 concert at the Vitoria-Gasteiz jazz festival in Spain, and she toured the album in full from September 2021.

Klein produced Half the Perfect World (September 12, 2006), which reached No. 33 on the Billboard 200 and No. 12 in the UK. It holds her duet with k.d. lang on Joni Mitchell's "River," songs by Leonard Cohen, Tom Waits and Serge Gainsbourg, and four original songs she co-wrote with Klein and others, with Sam Yahel on keyboards and Till Brönner on trumpet. She also recorded a live session at Abbey Road Studios in 2006 and won Best International Jazz Artist at the 2007 BBC Jazz Awards. Bare Bones (March 2009), again produced by Klein, was her first album of entirely original material, written or co-written with Klein, Walter Becker and Julian Coryell among others; it reached No. 12 in the UK and No. 71 on the Billboard 200.

She changed producers for Standing on the Rooftop (Decca, June 14, 2011), made with Craig Street in New York and featuring Marc Ribot, Allen Toussaint, Me'Shell Ndegéocello, Charley Drayton and Jenny Scheinman, with co-writes with the former Rolling Stones bassist Bill Wyman. The Blue Room (March 5, 2013) reunited her with Klein for a set of country and folk songs with string arrangements by Vince Mendoza, framed by its label as a response to Ray Charles's 1962 Modern Sounds in Country and Western Music. Secular Hymns (Impulse!, September 16, 2016) was recorded as a live trio set with the guitarist Jon Herington and the bassist Barak Mori in a parish church in Great Milton, England, on January 12 and 13, 2016, and produced by Peyroux herself. Anthem (Decca, August 31, 2018) returned to Klein and mostly original songs, with Chris Cheek on saxophones. Her most recent studio album, Let's Walk (June 28, 2024), was recorded in Rhinebeck, New York, in August and September 2023, produced by Elliot Scheiner, Herington and Peyroux, with all ten songs credited to Peyroux and Herington.

Peyroux sings in a low, unhurried alto that sits just behind the beat, and critics have regularly set her beside Billie Holiday, Ella Fitzgerald and Edith Piaf, a comparison made in the New York Times in 2013. She accompanies herself on acoustic guitar without a pick or finger picks and uses effects sparingly. Her repertoire is wider than jazz standards: early on it leaned toward 1930s and 1940s blues and swing songs associated with Bessie Smith, Billie Holiday and Fats Waller, and from Careless Love onward she built records around the song catalogs of Leonard Cohen, Bob Dylan, Hank Williams, Tom Waits, Joni Mitchell and Serge Gainsbourg, plus French chanson and, on The Blue Room, the country songbook that Ray Charles opened to jazz singers. Her records have charted at or near the top of jazz sales lists and her playing partners have been jazz musicians throughout, but her sound sits where jazz, blues, country and folk overlap, and some reviewers of the later albums have questioned how much of it counts as jazz.