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.
The song has been covered by Refused and British funk band 6ix Toys as well remixed by Pendulum (see Voodoo People (Pendulum Remix)) and other known and less known artists such as Eskimo, Alvaro and Shayning. Croatian cello duo 2Cellos have recorded an instrumental version for their album In2ition and have been performing it live on their subsequent tour. The track has also been a part of many soundtracks, such as Hackers, Dobermann, and others. In 2014 the song was covered by german based Alternative Rock Band Christiano and Gero M.