Andreone was born and raised in San Diego and attended Helix High School in La Mesa. After high school she spent time in Los Angeles, working during the day and singing at night.
Her first album, Veiled, produced by Rick Neigher, was released by RCA in 1996. It included the hit single "It's Alright, It's Okay" which charted in both the U.S. and Europe. It was introspective whereas her next album, Alchemy, was more sexual and intimate. Andreone's lyrics are often treatises on psychology, reflecting her interest in the subject.
In 2006, Andreone released an EP of new material entitled UNLABELED - The Demos, which contains a cover version of Beyoncé Knowles's "Deja Vu". On September 1, 2009, she released a new full length CD entitled Avalanche (written and produced by Andreone and Kevin Fisher). Avalanche includes a co-written duet with Dan Wilson (Semisonic, Dixie Chicks, etc.). A video was released for the first single, "Never Stop Trying".