Martin gründete Anfang der 1990er Jahre mit Jesse Harris die Formation Once Blue und nahm ein erstes Album auf. 1998 erschien ihr Soloalbum Thoroughfare. Ihr 2002 erschienenes Album Middlehope nahm die New York Times in die Liste ihrer Top-Ten-Jazz-Alben des Jahres auf; 2004 folgte People Behave Like Ballads auf dem Label Maxjazz. 2005 wirkte sie beim Album On Broadway, Vol. 4 or the Paradox of Continuity von Paul Motian mit. Auf dem Label Sunnyside Records erschien The Growing Season, das von Kurt Rosenwinkel produziert wurde; begleitet wurde sie von Larry Grenadier, mit dem sie seit 1997 verheiratet ist und ein gemeinsames Kind hat, und von Brian Blade;[1] das Album wurde mit dem Independent Music Awards als Bestes Folk/Singer-Songwriter Album ausgezeichnet.[2][3] Weiterhin betreibt sie (mit Becca Stevens und Gretchen Parlato) das Vokaltrio Tillery.
Neben ihrer Musikerkarriere arbeitet Martin als Executive Director des Kingston Land Trust im Hudson Valley. Sie lebt seit 2002 in Newburgh (New York), wo sie sich als kommunale Aktivistin betätigt.[4]
