La canción fue la primera en estar lista para el álbum y, de acuerdo a Perry y Aguilera, la interpretación lírica cuenta con inspiración de la también pista ""Boogie Woogie Bugle Boy"" de 1941 interpretada por la banda The Andrews Sisters. Igualmente, ""Candyman"" incluye una intervención de sonidos de cadetes militares extraídos de la marcha militar ""Tarzan & Jane Swingin' on a Vine"" del álbum Run to Cadence with the U.S. Marines, Volume II.