The band grew out of a partnership between Nathanson and Fowlkes in 1987, after the two had played with John Lurie's band The Lounge Lizards. Other regular members include vibraphonist Bill Ware, bassist Brad Jones and drummer E. J. Rodriguez; the group has often featured a violinist (Rob Thomas, Jim Nolet or, more recently, Sam Bardfeld). Guitarists Marc Ribot and David Fiuczynski played in earlier formations of the group. The album that is perhaps their masterpiece, the Hal Willner-produced In Love (High Street Records, 1994), features vocal contributions from Deborah Harry, Jeff Buckley, Jimmy Scott, Bob Dorough and Mavis Staples. Harry later became a regular member of the band, appearing on a number of follow-up albums, including Individually Twisted (which includes a duet with Elvis Costello), Costello also sings on another track without Harry. Recently the Passengers have recorded infrequently as a full ensemble, though the individual bandmembers' recent side projects tend to feature many fellow Passengers, as well as a similarly skewed musical sensibility.
In 2005, Nathanson composed a work commemorating the world's oldest object, a 4.404 billion year old zircon found in Australia. The work was performed by The Jazz Passengers at a "Rock Concert" held in Madison, Wisconsin in April of that year.