The video for the song was originally to feature Matt LeBlanc and Lisa Kudrow, from the sitcomFriends, but each pulled out nearly last minute, and had to be replaced with unknown actors. According to the commentary track on the DVD Barelaked Nadies, the male actor was Chris Hardwick, who later became famous for his work with Nerdist Industries. The video features a young girl who sneaks out of her bedroom to meet with an older man and go out with him for the night, only to be found by her mother and the police. At the end, the girl wakes up screaming, indicating that the scenario was only a dream. The performance portion of the video shows the band on a set with oversized props giving the appearance that they are within a shoe box kept under the girl's bed. The video is the first to feature new band member Kevin Hearn, who was not involved in the song's recording, but plays marimbas in the video nonetheless. The band later described the making of the video as a "fiasco".
The Shoe Box E.P. is a four-track E.P. which also contains an "enhanced" portion which features video clips and other multimedia elements playable on a computer. However, the disc was created using the pregap format which has not been supported by Windows or Mac OS for some time, rendering the data inaccessible to most users. The disc contains both the original Pirate Ship album version of "Shoe Box", as well as the radio remix, which includes an 8-bar instrumental introduction, and a remix of the song. The song also includes the B-Side "Trust Me", which also later appeared on the "If I Had $1000000" single; the version on the E.P. includes a count-in at the beginning that is edited from the later single version. The final track is a version of "If I Had $1000000" from The Yellow Tape (which previously appeared on the UK "Sandwich CD", which contains the first four tracks from "The Yellow Tape" in CD form).