Johnny Mathis had heard Erroll Garner play the song, and told him that he'd love to sing it if Garner had lyrics for it. Garner was in attendance when Mathis later recorded the song.
Although there were already several released versions, the Mathis version recorded in 1958 popularized this virtually unknown Garner song and inspired Clint Eastwood to use it in his movie Play Misty for Me, a low-budget film that proved to be a huge box-office smash. Eastwood, a fan of Mathis, ended up paying a nominal fee for the Garner recording in his film. The Mathis recording of "Misty" sold well over two million copies in the US alone.
The song is most associated with Mathis despite various recordings over the years by other artists. The Johnny Mathis version of the song was inducted into the Grammy Hall of Fame in 2002. His version of the song plays prominently in a ballroom dancing scene in the 2012 film Silver Linings Playbook.
In 1975 Ray Stevens released an up-tempo country rendition of this song. It is the title track of his twelfth studio album. Stevens recounted that the song was recorded on the second take when experimenting in the studio. His version won a Grammy in the category of Music Arrangement of the Year.
A 1976 episode of Saturday Night Live features a short film by Gary Weis—also entitled Play Misty for Me—which intercuts between different performances of the song by various lounge musicians and singers.
In a scene from the twentieth episode of the fifth season  of Magnum, P.I., Tom Selleck, as Magnum, is forced to sing the first few lines of the song (before being mercifully interrupted by gunfire) in a karaoke bar.