In 2004, when working on her second album, Amerie enlisted the services of producer Rich Harrison, who had helped produce and write her first album. In May 2004, Harrison heard "Oh, Calcutta!" for the first time and began working on the beat accompanying the ten-second back-and-forth breakdown between Meters drummer Ziggy Modeliste and guitarist Leo Nocentelli. Harrison said he loved the work of the Meters, especially Modeliste, commenting, "Ziggy, he's crazy." He processed the way the breakdown could be "flipped", added a bongo drum, a cowbell, and a ride cymbal, and sent it to Amerie. According to Harrison, they wrote and finished the song in two to three hours.