Peyroux was born in Athens, Georgia, and raised between Southern California, Brooklyn, and Paris. She began singing at age 15, when she discovered the Latin Quarter in Paris and became enamored with several street musicians. By 1989, she was working with a group of musicians called the Riverboat Shufflers, and after working for a while as a hat passer for the group, she began singing with them. She then joined the Lost Wandering Blues and Jazz Band at age 16, spending the next couple of years touring Europe while holding college in abeyance. That group formed the basis for her first album, for they performed the songs of Fats Waller, Billie Holiday, early Ella Fitzgerald, and others.

Though Dreamland was by no means a straight-ahead jazz album, Peyroux and her producers take a thoroughly modern approach to blues tunes from the 1920s and '30s. She interprets songs like Fats Waller's "I'm Gonna Sit Right Down and Write Myself a Letter," Billie Holiday's "Gettin' Some Fun Out of Life," as well as tunes popularized by Bessie Smith, like "Reckless Blues" and "Lovesick Blues." But unlike Smith or Holiday, who weren't known as songwriters, Peyroux also recorded three of her own tunes on Dreamland, "Always a Use" (on which she accompanies herself on guitar), "Hey Sweet Man," and "Dreamland."

It took another eight years, however (the reasons for which were never very clear), for her follow-up, Careless Love, to hit shelves. This time working with producer Larry Klein on Rounder Records, Peyroux explored a more contemporary and eclectic mix of covers, including Elliott Smith's "Between the Bars," Bob Dylan's "You're Going to Make Me Lonesome," as well as older songs like Hank Williams' "Weary Blues." It was very well received and made the 2006 release of Half the Perfect World, again a combination of covers and originals, highly anticipated. The record, which featured a duet with k.d. lang, included versions of songs by Serge Gainsbourg and Tom Waits, among others. Peyroux's third Rounder release was 2009's Bare Bones, her first to feature all original compositions by Peyroux (some shared with co-writers), was greeted with favorable reviews and was followed by an international tour. Peyroux took some time off, and emerged in 2011 with a download single that foreshadowed Standing on the Rooftop, her debut for the Decca imprint. The digital-only single offered a restrained yet elegant cover of the Beatles' "Martha My Dear," and the original "The Things I've Seen Today," co-written with violinist Jenny Scheinman. Standing on the Rooftop, released in June of 10011, was produced by Craig Street, and featured a core band of guitarists Marc Ribot and Chris Bruce, bassist Me'Shell Ndegeocello, and drummer Charlie Drayton. There guest appearances by Patrick Warren and Allen Toussaint, among others. Peyroux, wrote or co-wrote eight of the album's 12 songs; the covers included the aforementioned Beatles' tune, Bob Dylan's "I Threw It All Away," and Robert Johnson's "Love in Vain," as well as a the W.H. Auden poem, "Lay Your Sleeping Head, My Love," set to music by Ribot.