U're Still The One was first available as an audio stream on Prince's website Love4OneAnother.com in January 1999, credited to and Marva King. The track is a cover version of the track You're Still The One by Shania Twain (written by Mutt Lange and Shania Twain), which first appeared on the 1997 album Come On Over, and was released as a single in early 1998. In 2000, the track was also streamed on Prince's next website, NPGOnlineLtd.com.
Recording dates and studio are unknown, but it is likely that basic tracking took place in June 1998 at Paisley Park Studios in Chanhassen, Minnesota (the track was first played live on 20 June 1998 (a.m.) at the same show at which The War was recorded). Love4OneAnother.com announced that the track would be included on the single Come On (by the New Power Generation, indicating that the artist name would have changed), but it was not included on the final single.