Following the success of his first album in Australia, Andre was commissioned to record a second album with Melodian. However, Melodian believed that it would be wise to see if he could break the British market as well. Andre signed a joint deal with Melodian and the British record label, Mushroom UK, for his second studio album to be released in both markets. On 1 May 1995, a single, entitled "Turn It Up" was released to both markets, achieving Top 10 success on both countries' singles charts. However, the deal with Mushroom soon came under jeopardy when the label went into administration. Melodian pressed ahead with releases in Australia, releasing "Mysterious Girl" on 1 September 1995.
In January 1996, Mushroom announced that it had found a buyer for the label, meaning that it would not have to close, and that the joint deal was still in place. At this point, preparations for the album's release had been made in Australia. Three weeks before the album's release in Australia, a third single, "Get Down On It", was released, peaking in the Top 10 on the ARIA Singles Chart. On 1 March 1996, Mushroom announced plans to continue with its releases and the second British single, "Only One", was released. On 18 March 1996, Natural was released in Australia. Mushroom announced plans to release "Mysterious Girl" as the third British single on 24 May 1996; it, had not been released on the British market due to ongoing issues over the record deal. Mushroom also announced that, due to the problems caused by the label's proposed closure, it would be reworking the album for the British market. On 1 September 1996, a new single, "Flava", was released and three weeks later, the album was released. On the week of release, the album sold 200,000 copies, and become the fastest-selling album of the year. Two further singles – "I Feel You" and the title track, "Natural" – were released only in the United Kingdom, both entering the top 20 of the UK Singles Chart.
[1]