Stone quoted the lyrics "He's a one-stop shop / Makes the panties drop" and deemed it "nasty". Sputnikmusic's Amanda Murray described its lyrics as "dumb and cheekily vulgar". Jim McMillen played the trombone, while Ray Herrmann and Glen Berger performed the saxophone, and Chris Tedesco played the trumpet. Perry also played the piano, mellotron, bass, and served as the musical director. Nathan Wetherington played the drums. According to Aguilera and Perry, the song was a tribute to the Andrews Sisters' song, "Boogie Woogie Bugle Boy". Release "Candyman" was planned to be released as the second single from Back to Basics in late 2006. In July 2006, Aguilera told Seventeen that "Candyman" would be released as the follow-up single to "Ain't No Other Man". However, RCA Records chose "Hurt" to be released as the second single off the album; therefore, "Candyman" was released as the third. The song was sent to contemporary hit and urban contemporary radio stations in the United States on February 27, 2007. In Germany, the single was released for digital download on April 6, 2007. One day later, "Candyman" was released as a CD single in France and Germany. On April 10, the song was available as a CD in the United States. A digital EP was released via iTunes Stores in European countries consisting of Belgium, France, Germany, Spain, and Sweden. On the same day, the digital version of "Candyman" was released in France. It was also available as a maxi single there on September 1, 2007. In the United States, a remix EP was released digitally on May 1, 2007. Critical reception Billboard called the single "raunchy" and praised Aguilera's vocals, saying that "few popular vocalists could pull off such a laudable feat." Sputnikmusic's Amanda Murray deemed the song as "fun" and reminiscent of the Spice Girls' "The Lady Is a Vamp" from Spiceworld (1997). Sean Daly from Tampa Bay Times complimented Aguilera's vocals and its "X-rated lyrics". Pittsburgh Post-Gazettes Scott Mervis labelled it "the swingiest single since Brian Setzer jumped, jived and wailed," while Yahoo! Music critic Dan Gennoe called "Candyman" "a good-time 1940s big band romp", and Leah Greenblatt from Entertainment Weekly cited it as one of the few "pop-song highs" in Aguilera's career. AllMusic's Stephen Thomas Erlewine selected "Candyman" as one of the two outstanding songs on the second disc of Back to Basics, alongside "Mercy on Me". Lucy Davis for BBC