The video was filmed on location in New Orleans and cost around $500,000 US. According to the Scatman, "the day we shot the video was a day beyond all boundaries of time and space. Full of magic. All of the images together created the perfect atmosphere for showing the heart and soul of Louis Armstrong's roots". In the video Scatman, walking across a parking lot, sees the ghost of Louis Armstrong on the side of a building and the pair begin to duet. The bulk of the video takes place in a Louisiana street parade with Scatman and Louis riding along behind a marching band in a cadillac. Several children dressed up like Scatman are seen in the procession whilst onlookers wave Scatman and Louis flags. The video ends with Scatman looking up at Louis in the parking lot where it started. An alternate version of the music video was released with some parts of the video replaced with different scenes.