Written by Mick Jagger and Keith Richards, the song also carries writing credits for k.d. lang and Ben Mink. The song is known for its chorus, which sounds strikingly similar to lang's 1992 hit song "Constant Craving". Jagger and Richards claimed to have never heard the song before, only having discovered the similarity prior to the song's release. As Richards writes in his autobiography Life, "My daughter Angela and her friend were at Redlands and I was playing the record and they start singing this totally different song over it. They were hearing K.D. Lang's 'Constant Craving.' It was Angela and her friend that copped it."The two gave Lang credit, along with her co-writer Mink, to avoid any lawsuits. Afterwards, Lang said she was "completely honored and flattered" by receiving the songwriting credit.
"Anybody Seen My Baby?" is a typical song from the Bridges to Babylon-era Stones. It features wide-ranging inspirations, including sampling of hip-hop artistBiz Markie, making it one of the few songs by The Rolling Stones to include sampling (Bridges to Babylon is the only Rolling Stones album to include sampling). Bass and keyboards on the song is performed by Jamie Muhoberac while Waddy Wachtel performs acoustic guitar. The song has a distinctive R&B feel, driven by Muhoberac's bass. Jagger, Richards, and Wachtel perform electric guitars.
The song was a worldwide hit in 1997, reaching Top 20 in Europe, #1 on Canada's Singles and Rock charts and #3 on Billboard's Mainstream Rock Tracks. The video is perhaps best remembered for featuring Angelina Jolie. She appears as a stripper who leaves mid-performance to wander New York City. "Anybody Seen My Baby?" would go on to be the only track from Bridges to Babylon to appear on the Stones' 2002 career retrospective Forty Licks.