"Girls" was released as the album's lead single on 6 October 2008 in the United Kingdom, and features remixes by Fred Falke, Dennis Christopher and Funkerman. A moderate chart success around Europe in comparison with previous single, the song peaked in the top-three in Estonia, and the United Kingdom, and reached the top-twenty in Ireland and Turkey as well as the top-fifty in several countries including Slovakia, Ukraine and the Czech Republic. "Girls" is used as the one of two theme songs of Dagens Mand, the Danish version of Taken Out.
The music video for "Girls" was filmed on 28 August 2008 and directed by Daniel Wolfe, The video premiered on 4Music and Channel 4 on 6 September 2008. In the clip, bandmembers Amelle Berrabah, Keisha Buchanan and Heidi Range enjoy a girls' night out at a pole-dancing club, embraced by a "1980s disco style." It features the girls dancing and performing, focusing more on the other dancers during the chorus and on the girls while singing their verses. During their verses, Berrabah engages sensual dance moves with one of the fellow female dancers and Buchanan teases a male dancer.
While Big Brother: Celebrity Hijack contestant Latoya Satnarine is featured in a cameo appearance, Buchanan invited her boyfriend Dean Thomas to star in a supporting role in the video. As reported, Berrabah decided to have pole-dancing lessons before filming the video yesterday so she "wouldn't make a fool out of herself on the pole." After recruiting female fans to star in the video, producers denied accusations they were being unfair by failing to pay those who starred in the video. A spokesman for the band later stated: "No professional dancers are being asked to do anything for free. This is an opportunity for people who don’t dance for a living but who fancy their chances."
In the UK, the song entered two weeks prior to its physical release, on downloads, at number 8. The following week it climbed four more spots to number 4. The week of 13 October 2008, it climbed one spot to number 3. "Girls" marked their first lead single not to reach number 1 since their debut "Overload" in 2000. In Ireland, the song peaked at number 12.
Though the song was not officially released in the USA, it was used in commercials to promote American shoe store Payless in 2009. It was also reported that the song would be re-recorded with Jade Ewen's vocals to help promote US department store J. C. Penney in 2010. The original version featuring the third line up (Buchanan, Range and Berrabah) was already used in several commercials for J. C. Penney.