"Mysterious Girl" is the second overall single and third British single from singer-songwriter Peter Andre's second studio album, Natural (1996). It was written by Glen Goldsmith, Philip Jackson, Ollie Jacobs and Andre, and produced by Jacobs & Mubs. The song features guest vocals from Caribbean rapper Bubbler Ranx. It was first released as a single by Melodian Records in Australia on 14 August 1995 and was issued in the United Kingdom the same year, but it was not until a re-release in 1996 that the song became a commercial success there.

During its original 1995–1996 release, "Mysterious Girl" peaked at number one in New Zealand and number two in the Netherlands and the United Kingdom. It was also a top-10 hit in Australia, Austria, Belgium, Denmark, Germany, Hungary, Ireland, Sweden, and Switzerland. On the Eurochart Hot 100, the single reached number 11 in September 1996. In 2004, the song was once again re-released in Ireland and the UK, where it topped the UK Singles Chart following extensive promotion.

Clem Bastow from The Guardian described "Mysterious Girl" as "a perennial classic from that peculiarly mid-90s period where reggae and dancehall had invaded the pop charts. It holds its own (perhaps due to the guest spot from Caribbean rapper Bubbler Ranx) alongside Maxi Priest's That Girl, Shaggy's Oh Carolina and Chaka Demus & Pliers' ebullient cover of Twist And Shout."^[3] Pan-European magazine Music & Media wrote that "Andre's sunshine reggae single automatically conjures up tropical beaches, palm and coconut trees. As this summer seems to be without end, the chances look good for the Australian."^[4] A reviewer from Music Week rated the song three out of five, adding, "After patiently building a UK fanbase, Australian Andre could make the Top 10 with this pleasant reggae track."^[5] James Hamilton from the magazine's RM Dance Update described it as a "accomplished but derivative Chaka Demus & Pliers/UB40/Bitty McLean-ish catchy 85.9bpm pop-reggae roller".^[6]

The song reached the top of the charts in New Zealand and number eight in Australia, and it peaked at number two on the UK Singles Chart. Following a lengthy campaign on The Chris Moyles Show in 2004,^[7] and Andre's appearance on the British reality show I'm a Celebrity, Get Me Out of Here!, the song was re-released as the first single from Andre's fourth studio album The Long Road Back, peaking at number one in February 2004.^[8] In Ireland, "Mysterious Girl" reached number three upon its initial release in 1996, but the 2004 reissue saw the song reach a new peak of number two.^[9]

Filmed in Thailand, the music video for "Mysterious Girl" depicts Ranx and Andre on a beach. There are montages of several women, Andre, and Ranx dancing in a lagoon shirtless and in their jeans. The video was shot on on the Phi Phi Islands in Thailand and a Swiss Thai model called Champagne X (her name is Champagne Inthachak), who was a big star at the time, also played as a model in this video ^[10]. Andre is later seen dancing underneath a waterfall, a more iconic part of the video. Andre is last seen walking along the beach shirtless and later rolls in the sand as the sun sets. Clem Bastow from The Guardian wrote, "The video for the single was as much an advertisement for Andre’s personal trainer and spray-tan artist as it was a music video; the sight of him grooving in searingly blue tropical waters, proudly displaying his new look, was eye-popping (though not necessarily for the reasons he might have hoped)."^[3]