All of the music video is narrated, and the story is as follows. The group is at a police station and Q-Tip tells the story (i.e. the song). Initially, his mother wins a game show prize and goes on a month long cruise trip. After her departure, Q-Tip calls Ali and they take a road trip across America in Q-Tip's mother's car. The group gets lost on the way and Q-Tip asks a dwarf with a sombrero for directions. He tells them that they are in El Segundo and a mile away, there is a fast food station. They get there and eat, Ali has the fruit punch, Q-Tip pays for the lunch. Q-Tip is distracted by an attractive woman and forgets his wallet before they leave. The waitress then takes his wallet off the counter. They return home and Q-Tip drops Ali off at his home. Then, Q-Tip realizes that his wallet is missing and he rounds up the group to get it back. When they get back to El Segundo, they want to stay longer, and the video fades out.
There was a limited edition "transparent green" vinyl pressing of this single backed by a B-side track called "Pubic Enemy". This was a song about somebody catching an STD. The backing rhythm sample behind this track is "Bounce, Rock, Skate, Roll" by Vaughan Mason and Butch Dayo.
In the remake of the movie The Ladykillers (directed by the Coen brothers), the old lady Ms. Marva Munson is seen filing a complaint at the local police station. She says that her neighbors are playing "that hippity hop music" too loud and that the lyrics "I Left My Wallet in El Segundo" do not make any sense anyway. Later on, when meeting prospective tenant Professor G. H. Dorr (played by Tom Hanks), she brings up the title again as an example of music she does not like to listen to.
In the TV show Sleeper Cell, one of the member of the cell is a fan with this song, and sings it twice in the first season, even performing it on stage at a karaoke bar.