World Tour 2001. On October 26, 2008, Madonna performed a snippet of "Beautiful Stranger" as the request song during the Chicago stop of her Sticky & Sweet Tour. An a cappella version of the song was also performed during the Nashville stop of her Rebel Heart Tour in January 2016. In December 2016, Madonna performed "Beautiful Stranger" during her Tears of a Clown show as part of a benefit dinner for her charity, Raising Malawi, at Miami, Florida. Jon Auer, co-founder of the American power pop band The Posies, recorded a cover of the song on his 2001 solo EP 6 ½. Website Stereogum listed the cover at number five on their list of The 20 Best Indie Rock Madonna Covers. A 2007 folk music tribute compilation to Madonna, entitled Through the Wilderness, features a cover of the song by Golden Animals. Australian rock band DMA's covered the song during their BBC Radio 1 sessions with Annie Mac on March 8, 2016. Michelle Geslani from Consequence of Sound website praised the cover saying that it would "undoubtedly be hailed as yet another successful entry in DMA's young career" and described the cover as "easily tweaking the swirling, retro number into a psychedelic, arena-ready anthem". Michael Carr from Music Feeds magazine also praised the cover saying "Lending itself surprisingly well to the boys’ shoegazey brit pop treatment, the lads absolutely nail it... To be honest though, they kind of won on song choice alone". Most recently, American punk band Skating Polly released a cover of the song on the 2020 re-release of their album, The Make It All Show, as one of the bonus tracks. The band had previously covered the song on their 2016 tour. Track listing and formats US 12-inch promo vinyl 1 "Beautiful Stranger" (Calderone Club Mix) – 10:12 "Beautiful Stranger" (Calderone Radio Mix) – 4:00 "Beautiful Stranger" (New Club Edit) – 5:12 "Beautiful Stranger" (LP Version) – 4:22 US 12-inch promo vinyl 2 "Beautiful Stranger" (Calderone Club Mix) – 10:13 "Beautiful Stranger" (Album Version) – 4:21 "Beautiful Stranger" (Calderone Radio Mix) – 4:04 "Beautiful Stranger" (Calderone Dub Mix) – 6:22 US and UK promo CD "Beautiful Stranger" (William Orbit Radio Edit) – 3:58 "Beautiful Stranger" (LP Version) – 4:22 UK 7-inch and cassette single, European 2-track CD "Beautiful Stranger" (LP Version) – 4:22 "Beautiful Stranger" (Calderone Radio Mix) – 4:00 European, UK, Japanese, and Australian CD single