"Heading West" was written by Lauper, Billy Steinberg and Tom Kelly. The same team wrote "My First Night Without You, and the latter two wrote "True Colors", and "I Drove All Night". The song is about moving on from a past relationship, which was the overall theme of the album. A video was also released which was black and white and had Lauper in an empty field. The song was released outside of the U.S. The single was a minor hit in the UK. Cyndi Lauper said in an interview with O Globo newspaper that Heading West was a great song.
French Canadian pop star Mitsou covered the song as the title track for a 1992 EP and also released it as a single. She added a French spoken word monologue to the end of the song.