Candyman"" es una canción swing compuesta en compás de 4/4 y en la tonalidad de mi mayor, tiene un ritmo rápido a ochenta y seis pulsaciones por minuto, está escrita en el formato estribillo-verso-estribillo y los instrumentos que sobresalen en su melodía son el piano, el melotrón, el bajo, los tambores, el saxofón y la trompeta. Varias veces se escuchan sonidos de cadetes, entre ellas la primera intervención musical. En ""Candyman"", la voz de Aguilera abarca casi dos octavas, desde si 3 a re 5 que dura ocho segundos. La canción concluye en coda.