Nina Gordon left Veruca Salt in early 1998 amid rumors of stolen boyfriends and physical altercations with bandmate Louise Post. Post kept the Veruca Salt name, despite being the only remaining original member, and eventually released Resolver in 2000, the first Gordon-less Veruca Salt album.

Soon after leaving the band, Gordon demoed solo material in Boston with friends Kay Hanley and Michael Eisenstein from the band Letters to Cleo. In 1998 she sang on James Iha's solo album Let It Come Down on the song "Beauty". Shortly after she began recording with Eight Arms producer Bob Rock. The album, now titled Tonight and the Rest of My Life, was finished in early 1999 and was set to be released by Outpost Records, owned by Geffen Records, in August 1999. However, not all went smoothy, as Outpost Records was eaten up by the Geffen Records/Interscope Records merger and Gordon was left without a label.

Gordon wasn't label-less for long, however, as she was signed to Warner Bros. Records a few months later. Originally scheduled to be released in January 2000, Tonight was finally released June 27, 2000. The first single, also titled "Tonight and the Rest of My Life", did well on radio and has since been included in commercials for hit movies such as Chocolat and The Notebook. The second single "Now I Can Die", didn't do as well, and the third radio-only single "2003" actually performed better despite having little promotion and no video.

Gordon toured with David Gray as an opening act, and did a headlining tour with Palo Alto.

Tonight and the Rest of My Life peaked at a disappointing 123 on the Billboard Top 200. However, it floated around the mid-100s for months, and has sold close to 300,000 copies to date in the U.S. and 50,000 in Japan.

After Nina Gordon finished promoting Tonight and the Rest of My Life in late 2001, she took a break and began writing material for her second solo album. However, she didn't get into the studio again until late 2003. Reasons for this two year delay are uncertain, but Gordon says it was because she wanted to write a lot of great material. To tide fans over, Gordon released B-side material from Tonight on her website and a demo for a song called "The Time Comes", which was featured in the independent movie, Stealing Innocence.

Gordon began recording her second album with Ethan Johns in late 2003, and via her website stated she was excited with the direction the album was going, even though it was very, very mellow and sad. Gordon finished recording with Johns in early 2004 and stated that she had named it Even the Sunbeams, but little more about the album was ever revealed. A few months later, Gordon admitted she was unhappy with the album and she wasn't going to release it. The only song that surfaced from this recording session was "Lighter on the Moon", which was available on Nina's MySpace site. In April 2006, Gordon stated in the Chicago Reader, "It's a really sad and really slow record. I guess that’s how I was feeling at the time, but when I sorta snapped out of that, I thought, 'I don’t know that I want this to be the album I put out next.' It’s really a lovely record, but it didn't have the spirit of the records I've made in the past."

During this time, Gordon was performing at Largo in Los Angeles, for "Bring the Rock" nights, covering songs by N.W.A., Skid Row, Backstreet Boys and Phil Collins, as well as many others. Her cover of N.W.A.'s "Straight Outta Compton" gained her popularity on Internet music blogs. She also wrote a song with Fefe Dobson titled "Get You Off" for Dobson's album Sunday Love (on which Gordon also sang back-up), as well as a song for Courtney Jaye's album Traveling Light titled "This Is the Day", which she wrote with boyfriend Jeff Russo.