The album is a logical continuation of the previous one, Blue Light 'til Dawn. In an interview for New York Magazine Wilson explained that the album's name comes from the old Ashanti proverb—Sickness comes with the waning moon; the new moon cures disease. The album contains 10 songs; she wrote five of them.
A reviewer for Gramophone was generally positive about the album, praising Wilson's voice and her interpretations of the standards included. However, they said that compared to the originals, Wilson's versions may not be as powerful. They noted that with this album, Wilson appears to move away "from jazz heartlands or cutting edges and towards the embrace of 'pop cult' status." The reviewer particularly enjoyed "Skylark" (calling it "sublime") and "Last Train to Clarksville" ("a delight").
Rolling Stone's Geoffrey Himes reviewed the album positively. He noted its similarity to Wilson's previous album, Blue Light 'Til Dawn, but said that New Moon Daughter has more feeling and a darker tone. He said that Wilson makes Billie Holiday's "Strange Fruit" "her own". He noted the album's overall slow tempo as a weakness, wishing for a little more rhythmic diversity.Scott Yanow of Allmusic described Wilson's voice on the album as "quite bored and emotionally detached" but noted that she was "stretching herself".
Village Voice critic Robert Christgau was less impressed, writing that "most of these songs escape her attentions without a mark on them. Which isn't to mention the 'Strange Fruit' that establishes the surpassing weirdness of Billie's original, or the disastrous Monkees cover, designed to prove [Wilson] has a sense of humor I'm now convinced isn't there." A reviewer of Dusty Groove added "A pivotal set from Cassanda Wilson – and a record that firmly established her as one of the freshest new singers in jazz at the time! The album's awash in rootsy, dusky tones – and has an earthiness that's clearly inspired by older blues, but expressed by Cassandra in voicings that are more clearly jazz-based".