Proceeds of the single were announced to be donated to the Japanese Red Cross. The double A-side single contains a Japanese version of their 2010 Korean single "Run Devil Run" which was released as a digital single on January 25, 2011. "Mr. Taxi / Run Devil Run" was the first release by the group that contained an original Japanese song, as all previous releases by the group in Japan had been covers of their Korean songs, "Gee" and "Genie".
"Mr. Taxi / Run Devil Run" was released physically in Japan in three different editions on April 27, 2011: The regular edition only contains the CD. The deluxe first press edition contains the CD single, a mini-photobook of the members, a trading card, and a DVD containing the music video of "Run Devil Run" and a dance version. The limited period edition contains the CD, a DVD with the music video of "Run Devil Run", and a different photobook. The Japanese version of "Run Devil Run" was offered digitally through the Japanese iTunes Store starting January 25, 2011. The single was released internationally on April 23, 2011 through digital download on the iTunes store. In the United Kingdom, the single impacted BBC Radio 1's Essential Mix on October 27, 2012.
The girl group first performed "Mr. Taxi" live on May 13, 2011. They have since performed the song (both Korean and Japanese versions) on SM Town tours. In September 2012. while promoting "Oh!", they performed "Mr. Taxi" on "Hey! Hey! Hey! Music Champ" They then performed the song again as part of "Oh!"'s promotions on "Music Lovers".
"Mr. Taxi / Run Devil Run" set a new record for Girls' Generation, being their first Japanese single to sell 100,000 units during its first week of release. The single also managed to peak at the number one spot on BillboardJapan Hot 100 for two consecutive weeks. It reached a peak of eleven on the year-end singles chart of the Japan Hot 100. On May 25, 2011, "Mr. Taxi" topped the Taiwanese music chart, G-Music. The single also performed well on the Oricon Charts, reaching number on the Daily Single Chart, number two on the Weekly Single Chart, while reaching number forty-six on Oricon's Yearly Single chart. In the group's native South Korea, the single sold over 13,000 copies on the Gaon Albums Chart. "Mr. Taxi" performed well on its own, selling over 787,000 copies in 2011 on the International Single Chart of Gaon.
The teaser video for "Mr. Taxi" was released on April 22, 2011, and the music video was released on April 28, 2011, the dance version was released three days prior on April 25, 2012. The choreography for "Mr. Taxi" was handled by long-time collaborator Rino Nakasone, with Sim Jaewon.
The video begins with the girls dressed in yellow taxi driver outfits in front of a screen that flashes words and patterns in blue lighting. At the beginning of the second verse, it changes to the girls being dressed in black outfits (with differently colored piping for each girl), and dancing in front of a multicolored map of the world. Near the end of the second verse, and throughout the rest of the video, the video alternates between shots of the girls in their yellow outfits and their black outfits. After the second chorus, Sooyoung sings a rap bridge line "One, two, three, here we go! Oh!," which is followed by a dance break performed by Hyoyeon. The bridge continues with vocals by Yuri, Sunny, Sooyoung, Jessica, Tiffany and Taeyeon, after which there are more alternating shots between the two scenes (yellow and black outfits) for the final chorus, ending with the girls freezing in position in their yellow uniforms as the light fades out.
A music video of the Korean version was released to accompany the single's release made entirely from the group's performance of the song on their 2011 Girls' Generation Asia Tour, with a dance rehearsal for the song leaking in March 2012. As of July 5, 2015 the music video has reached 103,000,000.