A music video for the song was directed by director Ace Norton, who has previously directed videos for The Willows, Norah Jones and Death Cab for Cutie. The video was published on NME's website on 17 October 2007. Like the Beastie Boys' music video for "Intergalactic", it pays homage to Japanese kaiju movies. It shows two giant silver robots falling in love while other monsters and robots destroy the city they are in. The band themselves do not appear in the video.
The video was filmed over two days in Boston with American performance troupe Kaiju Big Battel. Some of the Kaiju (Japanese for 'strange beast') characters in the video are the Call-Me-Kevin, Grudyin, Unibouzo, Vegetius, Giii the Space Pirate and Steam-Powered Tentacle Boulder. One of the characters has striking similarities to a Cylon.