"Mr. Mysterious" is the third single from Vanessa Amorosi's album Hazardous. "Mr. Mysterious" was first performed live on TV at the 2009 Perth Telethon on 3 October 2009. Amorosi filmed the video for "Mr. Mysterious" in February and the song was released digitally in April 2010. Seany B, who is known for being the performer of the TV Rock hit "Flaunt It", makes a guest appearance in the song, doing a rap verse. Ms Amorosi describes the song as "a cheeky track about the guy you know nothing about but you can't get out of your head".
The first episode of Hey Hey It's Saturday in 2010 featured Vanessa Amorosi, performing her latest single "Mr. Mysterious". Before release as a digital single, the song was being used in the ads by the Network Ten for the British television drama series Merlin.
The video clip for "Mr. Mysterious" was shot in February by director Stuart Gosling. Gosling's Motion Cubism FX is used intensively throughout the video creating a fluid and mesmerising visual performance. Digital Pictures spent three weeks of post production to get the FX right. The video premiered on The Today Show and on Mornings with Kerri-Anne on 26 March 2010.