Her career began after moving to Los Angeles in University of Southern California's screenwriting program, also penning lyrics for a friend's songs. At a demo session for which the singer didn't arrive, Gray sang and the recording became a surprise success. She began performing in hotels in the area, eventually forming an after-hours called the We Ours. Gray then signed to Atlantic Records, who refused to release the album she recorded. A publishing contract with Zomba followed, as a result of her demo tape, and Gray signed another deal, this time with Epic Records, in 1998. The resulting album was 1999's On How Life Is, which gained commercial success slowly, though critical acclaim was nearly unanimous and she was nominated for two Grammy Awards (Best New Artist and Best Female R&B Vocal). "I Try", the first single, became a bit hit and had gone triple platinum by 2000. "I've Committed Murder" and "Why Don't You Call Me?" were minor hits.
The next year, Gray won the Grammy Award for Best Female Pop Vocal for "I Try", and was nominated for Song of the Year and Record of the Year. She then collaborated with Fatbloy Slim on Halfway Between the Gutter and the Stars, Black-Eye Peas and Slick Rick ("The World Is Yours" from Rush Hour 2 soundtrack), as well as acting for the first time in Training Day. With her fame growing, Gray became known for a series of bizarre antics, including being booed in 2001 after forgetting the words to the national anthem. In the midst of the controversy, Gray's The Id became a commercial failure, largely stalling on the charts, in spite of appearances by John Frusciante and Erykah Badu, though the single "Sweet Baby" hit #11. In 2002, she appeared in Spider-Man as herself and worked on Shaman, an album by Santana before relasing 2003's The Trouble With Being Myself''.