The video for Fish Heads was directed by Bill Paxton, who went on to appear in such movies as Aliens, Near Dark Predator 2, One False Move, Apollo 13, and Twister.