Lazarus erhielt ab dem Alter von acht Jahren klassischen Klavierunterricht. Mit zwölf Jahren begann sie, Tenorsaxophon zu spielen, das sie auch in der Schulband spielte. Mit 16 Jahren wurde sie Mitglied der American Youth Jazz Band, mit der sie 1980 eine Tournee durch Europa unternahm und auf dem Montreux Jazz Festival auftrat.[1] An der Harvard University studierte sie bis 1984 Englische Literatur, spielte daneben aber auch Saxophon und sang in Bands. Illinois Jacquet, der sie hörte, riet ihr, sich auf eine Karriere als Musikerin zu konzentrieren.
Nach dem Studium ließ sie sich in Frankreich nieder, wo sie zeitweilig Mitglied der Band von Jacquet war. Sie gründete eine eigene Combo, arbeitete aber auch mit Franck Amsallem, Riccardo Del Fra, Manuel Rocheman und Jacky Terrasson. Zunächst arbeitete sie in den Jazzclubs, dann auch auf Festivals wie Jazz in Marciac, Crest Jazz Vocal oder dem JVC Jazz Festival Paris.