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."