The original video was directed by Walter Stern and Russell Curtis. It was filmed on location in Saint Lucia and it showed Leeroy Thornhill as a voodoo priest. This version included scenes featuring real witch Doctors, but these were cut because of problems with television censorship. A number of other more graphic versions of the video are available, one of them appearing in the Prodigy's Electronic Punks documentary.
The British release included a remix by The Chemical Brothers who at that time called themselves "The Dust Brothers" in honour of an American producer duo of the same name. When "Voodoo People" was to be released in the USA, and due to the British Dust Brothers' rising popularity, the American Dust Brothers threatened a lawsuit if they didn't change their name. The British duo changed their name to "The Chemical Brothers", and the remix on the American Mute release was renamed in accordance. A small sample in the remix was also reversed on the American release due to copyright issues.