Following the success of his first album, Andre was commissioned to record a second album with Melodian. However, Melodian believed that after the success received in Australia for his first album, that it would be wise to see if he could break the British market as well. Andre soon signed a joint deal with Melodian and British record label Mushroom UK, which would see his second studio album 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' respective 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 they had found a buyer for their label, meaning that they would not have to close, and that the joint deal was still in place. However, at this point, preparations for the album's release had been made in Australia. Just three weeks before the album's release in Australia, a third single, "Get Down On It", was released, peaking within the Top 10 on the ARIA Singles Chart. On 1 March 1996, Mushroom announced plans to continue with their releases, and the second British single, "Only One", was released. On 8 March 1996, the album, entitled 'Natural', was released in Australia. Plans for a British release were still ongoing at this point. Mushroom soon announced plans to release "Mysterious Girl" as the third British single on 24 May 1996, as at the time of release in Australia, the track had not been released on the British market due to ongoing issues over the record deal. Mushroom soon announced that due to the problems caused by the label's proposed closure, they 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 exclusively in the United Kingdom, both of which entered the Top 20 on the UK Singles Chart.