The original recording of "When the Stars Go Blue" on the Gold album received little attention by critics due to the timing of the release and Adams' overwhelmingly large and ranging catalog. The Gold album was released on 25 September 2001, with a lead track called, "New York, New York", which became a radio hit in the wake of the attacks on the World Trade Center. In the next year, Adams produced material that could have made up four albums. Critics have been known to be averse to reviewing Adams' works due to the large quantity and variety of his works. Adams has had numerous attacks for his "genre hopping" and has been labeled as "musically bipolar" by critics. It wasn't until Tim McGraw's cover that the song got critical attention. When Adams performs "When the Stars Go Blue" in concert now, critics note Adams' "masterful ballad" performances, and "When the Stars Go Blue," is the "most gorgeous ballad on the [Gold] album".
In 2006, the song was released by Tim McGraw as the first single from his album Tim McGraw Reflected: Greatest Hits Vol. 2. Heribert Severing, creator and writer of severing.nu, included McGraw's version of "When The Stars Go Blue" on his list of the top Country singles of 2006.
The video was directed by Sherman Halsey. It features McGraw performing in a snowy background surrounded by clusters of pine trees. It was shot in Crivitz, Wisconsin. The video was shot in black-and-white. Throughout the video, several reflections of people can be seen in the trees. In the end of the clip, McGraw starts to walk backwards, turns around, starts to run, then disappears, leaving only a trail of footprints behind. The version of the song in the video is edited to fit into the time of 3:19. It was released in April 2006.
Irish/British girlband Wonderland performed the track for their debut performance on television in Ireland. Both live and studio version is available on Youtube. The recorded studio version was included the band's debut album Wonderland released in United Kingdom and Ireland on 6 June 2011.
Nicole Lexi Davis, a 70's-styled acoustic folk rock musician from California, sang a rendition of "When The Stars Go Blue" at Tootsies Orchard Lounge in Nashville, Tennessee in August 2009.
Performed by Blake Lewis on American Idol Season 6, originally airing on April 17, 2007. In an interview on that episode of American Idol, Lewis incorrectly attributed the song to Tim McGraw. His cover of the song made it to #92 of the pop charts in 2007.