The band formed in 1999, when future members Marc Terenzi and Ben Bledsoe met at a party. Terenzi and Bledsoe met future band mates Patrick King and Michael Johnson at an industry party. The four got together and after subsequent members joined and left, settled on fifth member Michael Horn, who Bledsoe had found through his vocal coach. The five young men tried to get signed to record label on their own, but ended up being turned down by most of the major labels. They originally worked with manager Veit Renn and recorded several songs. However, the band, eventually frustrated, turned to Lou Pearlman, who had had success with some of the biggest boy bands in the world. Renn was not pleased with this and sued. The outcome of the case is unknown, though the band did eventually stay with Pearlman. The band was signed under Transcontinental Records and released albums under that label in the United States, and Sony BMG abroad.
Unlike most boy bands who are vocal groups, the members of Natural all played instruments. Renn claims he was the one who insisted they learn instruments, spending $75,000 on their training. However certain members such as Horn and Terenzi claim they had been playing since childhood. Bledsoe played bass and was one of the lead vocalists, while Terenzi played guitar, as well as being the second lead vocalist. Horn became J Horn, to avoid confusion. He played piano, and was the final lead vocalist, though in subsequent years as he withdrew from the band he was featured less, while Patrick King also played guitar, and Johnson played the drums. The band realized that they couldn't promote themselves very easily without having to bring their instruments with them everywhere they went, so they started performing a cappella versions of their music. This method was successful, as their first show at the House of Blues in Orlando, FL was completely sold out. Soon after, they kept building, by Bledsoe learning how to beat box and do vocal bass lines within the band, in the a cappella setting. Then, after realizing that both Johnson and King had extensive training in dance, the band added a few up tempo Rock style dance songs to their set. These were only seen on their tours, as it was a way to keep the show changing and more interesting. They would also switch instruments to allow one singer to have more front time for a specific song.
In the summer of 2000, Pearlman hired Steve Kipner to write Natural's first single, "Put Your Arms Around Me". He also struck a deal with teenage accessories store Claire's. The store sold the single as an extra with a $12 or more purchase. A join tour with The Monkees in conjunction with Claire's followed. However, the single never actually charted on the Billboard Hot 100. The single became #3 on the Billboard Hot 100 Single Sales Chart, yet that had little impact on the general public. Natural attempted promotions in the United States several times in the next few years, though sporadically. Such promotions included several interviews and features in POPstar Magazine, performing in the Macy's Thanksgiving Day Parade 2001, performing medley tribute to the Bee Gees as part of ABC's 'Disco Ball' in 2003, and at one point a mall tour with Saks Fifth Avenue, they still never charted or had successful radio play outside of Orlando.
Pearlman decided to wait on the American release, and the band went back to Germany where their first album Keep It Natural was released. The album exploded onto the top of the charts in many territories across the world, and debuted at number two in Germany. This was only the beginning. The band continued with eight top 10 singles and multiple number ones in the country, and the tours grew from dlub-sized venues to arena tours. The single and the album did quite well, and tours followed around Germany. The band also experienced success in Malaysia and Japan as well as the Philippines. These were the Asian countries where they had the most success, winning several awards. However, the days of popboy bands had long since passed in Germany, and the members of the band were adamant about trying out their own new sound. With each of their poppier singles progressively dropping on the charts - including "Runaway", which only reached #40 - the guys felt it was time to change. "Runaway" is notable for having been written by Danny O'Donoghue and Mark Sheehan, who later went on to become members of worldwide chart-topping band The Script, having themselves started in an American boyband - Mytown. The band tried to release "Paradise" as a single, but Pearlman was hesitant about the new sound. Some form of a compromise was reached when "Paradise" was released as a limited edition single in their hometown, and a British release was planned for November 2003, however minus local Orlando airplay in the summer of 2003, nothing ever became of the single release.
For unknown reasons, certain lyrics were changed for the release of certain singles. For example;
"Put Your Arms Around Me" has the original chorus line of Come lay down beside me, though for certain video versions it was changed to Always be beside me for reasons unknown, despite other lyrics such as 'I'll be here when the dawn meets the day' seeming more risque then that particular line. The original version is featured on the album.
"I Count the Minutes" has the original lyric, performed during the FOX Family concert, of My lips are hungry for the taste of you; I cant wait, cause I live for the love that we make. When the album was released, the lyric was changed to My heart is aching cuz I'm missing you; I cant wait, cuz I live for your love every day. No reason was given.