Formati nel 1987 dal sassofonista Roy Nathanson e dal trombonista Curtis Fowlkes (entrambi ex membri del gruppo no-wave Lounge Lizards), i Jazz Passengers debuttarono con Broken Night/ Red Light (1987), che mostra la loro evoluzione da duo a band a tutti gli effetti, con il vibrafonista Bill Ware, il bassista Brad Jones, ecc.
Il loro ingegno dadaista, l'iper-fusione di musica etnica, rock e funk, l'improvvisazione libera e le eleganti citazioni postmoderne sbocciarono in Deranged & Decomposed (1989) e soprattutto in Implement Yourself (1988), contenente Indian Club Bombardment e con il chitarrista Marc Ribot e il violinista Jim Nolet.
Live at the Knitting Factory (gennaio 1991), con Yuka Honda al campionatore e Marcus Rojas alla tuba, conteneva Tikkun.
Un po' troppo anarchico persino per gli standard di Frank Zappa, Plain Old Joe (1993) segnò la fine dell'era epica.
In Love (1994) vide la partecipazione di una serie di cantanti (da Deborah Harry dei Blondie ai cantautori Freedy Johnston e Jeff Buckley).
Individually Twisted (1996), che includeva due duetti di Harry con Elvis Costello, e Live In Spain (luglio 1997), che includeva Lady Butter, furono presentati come collaborazioni tra i Jazz Passengers e Debbie Harry.
Quest'ultimo fu il primo album senza Fowlkes.

Reunited (2010) è stato il loro primo album in dodici anni.

Il live Nearness And You (giugno 2015) documenta il settetto acustico dei Jazz Passengers formato da Roy Nathanson (sassofoni contralto, soprano e baritono, voce), Arturo O'Farrill, Anthony Coleman e Myra Melford (tutti al pianoforte), Marc Ribot (chitarra acustica) e Curtis Fowlkes e Lucy Hollier (tromboni).