Beautiful Strange was first available as a video of a studio recording ending the Beautiful Strange home video, with a short segment of the recording session included as a prologue to the home video (the home video was broadcast in full almost a year earlier, however, on the UK TV channel Channel 4). In 2001, a remixed version was included as the eleventh track on Rave In2 The Joy Fantastic, the companion album to Prince's 23rd album Rave Un2 The Joy Fantastic (his sixth album using the name ). It was the only track on the album not to have been included on Rave Un2 The Joy Fantastic.
While specific recording dates are not known, basic tracking likely took place in mid-1998 at Paisley Park Studios in Chanhassen, Minnesota. Remixing likely took place in late 1999 or 2000, also at
Paisley Park Studios. The song was included as the title track on the 1998-9 album Beautiful Strange, but little is known about the album, which remains unreleased.