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(It is revealed on the BNL DVD Barelaked Nadies by listening to the band commentary that the male actor was the host of MTV's Singled Out, none other than now-famous nerdist Chris Hardwick). 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, from having that as a nightmare. The band-performance portion of the video sets the band on a set with over-sized 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).