The song was inspired by the story of a childhood friend of Lauper, who in her teens got pregnant, had a back-alleyabortion, and died as a result. The song was co-written with Mary Chapin Carpenter. Lauper was a childhood fan of Elton John, and as a tribute to him, "Sally's Pigeons" contains references to "Tiny Dancer," a song that Lauper has revealed to always make her cry. Whether a coincidence or not, but Bernie Taupin's 1995 song "Blessed" plays off the words star and hat.
The video also featured a then-unknown Julia Stiles. One of the "little girls in pony-tails" described in the song's lyrics is played by former Ford model Valerie Mendler. Sally is portrayed by Blaze Berdahl, who is best known for playing Lenni Frazier, a character on the PBS television series Ghostwriter.
Mike DeGagne of Allmusic spoke of the song in a review of the Hat Full of Stars album, stating "The title track and "That's What I Think," along with "Sally's Pigeons," make for the most promising of the 11 cuts."
In the December 23, 1995, issue of the Billboard Magazine, the song was mentioned in "The Critics' Choice" section, where the magazine's editors and writers chose their top 10 records, videos and live concerts of 1995. Chuck Taylor, the magazine's radio editor, listed Lauper's 1995 compilation Twelve Deadly Cyns...and Then Some at #6 of his top ten albums, stating "Kickin' longform video, too. Discover of "Sally's Pigeons" is a high point. Thanks, girl, I had fun."