"All the Right Friends" is one of the earliest songs written by R.E.M., written by Peter Buck and Michael Stipe in 1979 before meeting their future bandmates, according to Peter Buck's liner notes to the band's In Time compilation album. Like all R.E.M. songs, its composition is credited to all members.

The song was recorded for Murmur in 1983, but was left off the album. In January 1993, the European reissue of Dead Letter Office, a B-side album compilation, included that recording, along with an acoustic version of "Gardening at Night". The song was also recorded during the Reckoning sessions, but not used (though bootlegged), and later recorded during the Lifes Rich Pageant demo sessions (this version was included on the bonus disc of the 25th Anniversary edition of the album).^[1]

In 2001, director Cameron Crowe released the movie Vanilla Sky, starring Tom Cruise. R.E.M. were approached with the idea of them contributing a rock song to the soundtrack. According to Peter Buck, they were approached "about eight days before they needed it", and they had loads of material left from Reveal, but they wanted a rock song, and their manager Bertis Downs had liked "All the Right Friends", so they recorded it. Slightly different from the other version (with most of the original lyrics missing), the song was, in Peter Buck's vision, recorded as if they were recording it for the Chronic Town EP, as Buck noted on the sleeve notes to the band's 2003 In Time compilation album.

The song was recorded on October 23, 2001, in Seattle's Bad Animals Studio's "Studio X" while R.E.M. were in town for a performance at the Groundwork Benefit the previous day and, that evening, at the Crocodile Café. On an R.E.M. special of The South Bank Show, which aired in May 2002 on the UK's ITV, Buck is seen recording a guitar overdub for the song, then, upon completion, the camera follows him into the control room to evaluate the recording.

In addition to the Vanilla Sky soundtrack album, the re-recording is included on R.E.M.'s 2003 Warner Bros. Records compilation, In Time: The Best of R.E.M. 1988-2003. The original 1983 version of the song recorded for Murmur was internationally released on the expanded edition of the 2006 EMI compilation, And I Feel Fine... The Best of the I.R.S. Years 1982–1987.