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. The 1975 country version by Ray Stevens 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 titled Play Misty for Me), which intercuts between different performances of the song by various lounge musicians and singers.
In an infamous 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, in what has become notorious as one of the worst renditions of the song ever committed to film.
The 1986 Cheers episode "Cliffie's Big Score" has a scene where Cliff Clavin (John Ratzenberger) sings the song while attempting to seduce Diane Chambers in his car.