The video for "My Moon, My Man" takes place in an airport (Pearson International Airport in Toronto). But because of the lighting, the beginning of the video had to be re-shot, in an upstairs of a bar, near the airport. Feist is walking down the moving pathway, dancing back and forth, leaving her suitcase behind in the end, and returning to dance some more. Near the end of the video the lights change from normal lighting to a blue tinted lighting, turning on and off in rhythm with the song. The ending (which includes a walk and an opening of the door, unseen) with "The Park" is kept.