The basic recording of All My Dreams took place on 28 April 1985 at Sunset Sound in Hollywood, California (four days after Holly Rock, the same day as Kiss).
It was included as the ninth and final track on a 1 May 1985 configuration of Parade, but was removed before the album’s release. The track was later included as the nineteenth and final track on a 3 June 1986 configuration of the album Dream Factory, and kept as the eighteenth and final track on the 18 July 1986 configuration of the album.
When Prince decided not to proceed with the album after disbanding the Revolution, and concentrated instead on Camille and Crystal Ball (both of which were also aborted), he decided not to include the song. It was then shelved until it was released in September 2020 as the third track of Vault Tracks part 1, one of the discs with previously unreleased tracks included with the Sign O’ The Times Super Deluxe Edition.
The track was mentioned as a possible track for the 1998/1999 album of Revolution-era tracks, Roadhouse Garden, but this remains unreleased. Artwork has been posted online for an NPG Music Club album titled All My Dreams, which likely includes this track, but nothing else is known about this album.
A portion of a distorted spoken section of this song was later reused in Acknowledge Me.