The single peaked at #6 in the United Kingdom, and reached #1 in New Zealand. The song is notable for its chorus lyrics 'get the cool shoeshine', which later came to be the slogan for Shoe Zone.
The single released was accompanied by a completely new version of the song, called the "Soulchild Remix", which was produced by music producers Damien Mendis and Stuart Bradbury. Mendis was asked to remix a track off the album in the hope that it would give it crossover potential, in the same way as the Ed Case remix of "Clint Eastwood" had. Mendis was given a copy of all their demos and finished tracks for the album, being told to "pick [a song] that you can produce, remix or whatever into a hit single". Mendis was unsure which track to choose, and only when he was told that Jamie Hewlett was already working on the video for "19-2000", did he make his decision. The remix appears to utilise the drums from "Sing a Simple Song" by Sly and the Family Stone. The remix is basically a faster, more upbeat version of the song, but with re-recorded vocals as opposed to the sped-up vocals of "Clint Eastwood: Ed Case Refix". The remix appears as a bonus track on the original version of the album, as well as being the first track on G Sides. From 2002, this version replaced the original version on radio stations and television stations. Another version of the song, entitled the "Gorillaz on My Mind Remix", features US rapper Redman, and appears on the soundtrack of Blade II.
The video, directed by Jamie Hewlett and Pete Candeland, is animated, both in 2-D and 3-D. It features Gorillaz riding in their Dune Buggy along a twisted highway, encountering roller coaster style loops, a killer UFO, when Murdoc decides not to take an exit leading toward a church, and a giant moose. Murdoc tries to blow up the moose with a pair of missiles, but the moose sneezes right before impact, sending them back to the car, which explodes and skids along the highway on fire. The missile targeting system is a reference to the X-wing targeting system the Rebel Alliance uses in the Star Wars film series to blow up the Death Star. The members of Gorillaz appear to have black ash all over them from the blast. A stylized duck head, an Easter egg in early Gorillaz videos, can be found on the heads of the missiles right before they are sneezed away by the moose. In between these various encounters the Gorillaz pass and perform things in time with the rhythm—such as a field of oil rigs, or the light posts passing them at the beginning, and a couple of sections where the buggy does several versions of the wheelie and even appears to break the sound barrier. There are two versions of this video, one to fit the original mix and one to fit the soulchild remix. Both videos are almost identical, except for a few minor changes in order for the two songs to sync up with the video. On the motorway, there are signs to the Overlook Hotel, a reference to The Shining, and Camp Crystal Lake, a reference to Friday the 13th. It was shown in the MTV Cribs tour of Kong Studios that the buggy actually survived the blast, and now sits in the Kong Studio's parking lot where, upon passing it, Murdoc commented that it "costs more than a space shuttle".