All Along The Watchtower is a cover version of the song by Bob Dylan, which first appeared on his 1967 album John Wesley Harding, and was released as a single the following year, although Prince's version is more in line with the more popular version of the song as performed by The Jimi Hendrix Experience, released on their 1968 album Electric Ladyland and released as a single in 1968. The song is written by Bob Dylan. Prince's version of the song is in a medley with Best Of You by Foo Fighters.
A studio/rehearsal version of the All Along The Watchtower / Best Of You medley was debuted on The Howard Stern Show on 29 January 2007, a few days before Prince's performance at the Pepsi Super Bowl XLI Halftime Show, where the medley was also performed. The broadcast contained only snippets of the track, however, with the host talking over the track declaring his excitement. It has been performed live a number of times since, but the version played on The Howard Stern Show has not been released.