Thom premiered the song on november 1st 1993 on the Canadian TV program 'Musique Plus'. At this point the song was titled 'Three-Headed Street Spirit' and the "Immerse Your Soul In Love" ending had yet to be written:



Thom said that the song was inspired by The Famished Road by Ben Okri. In that book there is a three-headed spirit that leads the main character down a road, so that's apparently where the title came from.
The song was included on this august 1994 work-in-progress tape compilation under the working title '(Fade Out)'. The handwriting is Thom's. Since a note like "rough" or "not finished" is not written next to the title, the cassette appears to contain the finished version:

Jonathan Glazer had been bugging the band to let him produce the video if this song ever became a single. They let him, with spectacular results.
Until 'Paranoid Android', this was the band's best-placed chart entry.