The song was recorded without Eminem by Gorillaz and D12[3] in Damon Albarn's personal studio in West London. The track came about after the 9/11 terrorist attacks in New York City, leaving the band stranded in England; Albarn invited the band to his studio while they were there and played them an early demo of the track. Albarn had always wanted to experiment with Middle-Eastern music, and felt that this song would be perfect. D12 added additional production to the song, before laying down their verses. Terry Hall appears on the song as a vocal harmony with Albarn for the song's chorus. Albarn and Hall had previously spoken about collaborating together, however when Hall revealed that he had been taking singing lessons from a Middle-Eastern singer, it inspired Albarn to take the song in a different direction.
The video features the same visuals as "Clint Eastwood" and "19-2000", but with a different background. The track features D12 running towards the camera. Terry Hall does not appear in the music video.
