1955年12月４日、ミシシッピ州ジャクソン生まれ。父親が熱心なジャズ・ファンで、幼い頃よりジャズに親しむ。ピアノとギターを学ぶ。ハイスクールではジョニ・ミッチェル、ボブ・ディラン、ジェームス・テイラーなどフォーク／ロックに興味を示す。ニューオリンズでエリス・マルサリスと出会い、ジャズ中心の活動になる。1982年にニューヨークへ進出。M-Baseを推進するスティーヴ・コールマンと出会い、コールマン率いるフリー・ファンクのバンドで活躍。1985年にファースト・アルバム『ポイント・オブ・ビュー』(ＪＭＴ)を録音した。ジャズ、フリー・ファンク、エスニックなどがミックスされた独自の個性を確立して、次々に話題作を発表する。1993年にブルーノートと契約。第１弾『ブルー・ライト』がセンセーショナルな話題を呼び、ブレイクを成し遂げる。ブルーノート移籍後、カサンドラはブルースに根差したオリジナリティあふれる音楽を志向した。『ニュー・ムーン・ドーター』(1995年)では、グラミー賞の最優秀ジャズ・ボーカル・パフォーマンス受賞。また、ダウンビート誌の国際批評家投票では女性ジャズ・ボーカルのウィナーの常連となる。2001年にはタイム誌で「ベスト・シンガー」に選出、ジャズを超えて不動の評価を得る。その以降、ジャッキー・テラソンとのコラボレートしたスタンダード集『テネシー・ワルツ』(1997年)、マイルス・デイヴィスへ捧げた『トラヴェリング・マイルス』(1999年)、ブルース志向を強めた『ベリー・オブ・ザ・サン』(2002年)『グラマード』(2003年)を発表、いずれの作品も絶賛を博している。