En 1994, Nathanson compuso un buen número de temas para el álbum Jazz Passengers in Love, producido por Hal Willner y Huge Dwyer.

Estos temas fueron interpretados por cantantes como Jimmy Scoff, John Kelly, Freedy Johnston, Bernard Fowler, Jeff Buckley o Deborah Harry.

Su tercer álbum, I Could've Been a Drum, fue publicado en el sello de John Zorn, Tzadik Records.

The Fire at Keaton's Bar & Grill, fue su cuarto disco como líder en solitario, el primero para Six Degrees Records, en marzo de 2000.

Como actor, ha intervenido en películas de Chantal Akerman, Jim Jarmusch y Elaine May, así como en varios proyectos teatrales.