メイシーは1970年にナタリー・マッキンタイア（Natalie McIntire）としてオハイオ州カントンに生まれました。子供の頃は、両親のレコード・コレクションから取り出されてはよくかかっていたという、スティーヴィー・ワンダー（一番のお気に入り）、マーヴィン・ゲイ、アレサ・フランクリン、パティ・ラベル、ジェイムス・ブラウン、スライ＆ザ・ファミリー・ストーンなどがお気に入りでした。そんな小さい頃から音楽好きなメイシーは、７年間もの間クラシック・ピアノを学びました。でも人前で歌うことは全くなかったそうです。理由はメイシー自身の声。今では考えられませんが、小さい頃のメイシーはとても無口で、引っ込み思案で、自分に自信が持てなかったのです。メイシー曰く、「このすごく変な声が悩みでね。しゃべるたび、みんなにからかわれていたくらいなのよ。子供だから、どんどんそうなると話すのが嫌になって、しゃべらなくなって…。そんな私が今じゃ歌手だなんて思ってもいなかったわ」
ティーンエイジャーになると、ソウル・ミュージックに引き続きドップリ浸かりつつも、オールド・スクール・ヒップホップの洗礼を受ける。その一方で、黒人生徒がほとんどいない全寮制の学校に２年間過ごしたため、オープン・マインドなメイシーは、ロックにも触発される機会を持ち、結果さまざまな音楽からの影響を受けて成長していきました。
そして、メイシーは映画の世界では有名な南カリフォルニア大学(USC)で映画の脚本を学ぼうとLAへ引っ越すことに。そこでの友達のミュージシャンに頼まれて、初めて作詞にチャレンジすることに。メイシーはその曲のデモ・レコーディングに立ち会いに行くも、ヴォーカリストが無断欠席。すると、友人から「かわりに歌ってくれない？」と頼まれてしまう。元々自分の声にコンプレックスを抱くメイシー、ためらいながらも引き受けるとこれがなかなかいいじゃん、と大評判。すると次第にメイシーへのオファーが増え始め、歌う機会が増えていき、地元でも一躍有名な存在に。当時のメイシーはこの状況が信じられなかったが、このデモへの参加が結果的には音楽への道を選択するきっかけとなった。メイシー曰く、「みんな嘘つきなんじゃないかと思っていたの。自分ではお喋りすら避けていた女の子のままのつもりだったし、ただの暇つぶしくらいの感覚だった。LAの本物のライヴハウスでショーをやり始めてちょっと真剣に考えはじめたわ」
その頃、ハリウッドに小さなコーヒーショップ「the We Ours」をオープンさせる。メイシーにとっては、深夜スタジオを出て、みんなで気軽に楽しむ店がほしいという理由から、「なら自分ではじめちゃえっ！」と店を開き、大袈裟なことは当初全く考えなかった。しかし、「the We Ours」は思いがけなく大きくなっていく。メイシー曰く、「そう、口コミでどんどん広がってね。The RootsとかTrickyとかも来るようになって溜まり場みたいになっていったのよ」。ここには誰もが歌い手になれるようマイクをおいて、メイシー自身や現地のライヴバンド、ＤＪなどもここで集まってはライヴを開き、ちょっとした話題のスポットになっていった。メイシーの友達がさらに友達を呼んで、その輪がどんどん広がっていった。メイシーもここでパフォーマンスの腕を磨いたという。
そしてメイシーはめでたくアトランティック・レコードと契約。しかしここからメイシーには人生の挫折が待っていた。まもなくできあがった作品はアトランティックにNGを出され、打ちのめされる…。さらにプライヴェートでも３人目の子供を身籠もっているさなか夫と破局、いったん故郷カントンへ戻ることに（註：メイシーは現在８歳、７歳、５歳の子供の母でもあります）。
しかし世はメイシーを見捨てはしなかった。LAを離れてからも彼女のデモテープはいろんなところに廻って評判になっていったのである。そして、ゾンバと出版のディールを結ぶために再びLAに戻ると、９８年４月再び争奪戦の末、Epic Recordsと契約を結ぶことになった。その際には、キダー・マッセンバーグ（モータウン社長：ディアンジェロ、エリカ・バドゥ、インディア・アリー等の発掘人として有名）も名乗りを上げていたという。