Her first studio album, 1993's Evolution, was the one that really made her name in the jazz community. Featuring guests like Joe Henderson, and Joe Louis Walker, it helped her win the honor of Talent Deserving Wider Recognition in that year's Down Beat critics' poll (which she would repeat in 1995 and 1997). Her follow-up album, 1997's Straight Up With a Twist, was her most eclectic outing yet, featuring often quirky interpretations of standards, plus guest appearances by Roy Hargrove and Charles Brown. Taking her time between recordings, Margolis returned in 2001 with her fourth album, Left Coast Life, which once again received highly complimentary reviews. Her next album was Heart & Soul: Live In San Francisco (2004) taped in front of a packed house at the old On Broadway Theater in San Francisco's North Beach. Highlights include: "A Sleepin’ Bee," her incendiary scat tour de force on "Summertime," a bluesy romp though Mose Allison's "Your Mind Is On Vacation" the funky, joyful re-working of "Surrey With the Fringe," her sweet, poignant celebration of "Secret Love," the blazing version of "My Favorite Things" and her achingly romantic interpretation of the title track.