Formation and early works
Stargate began in 1996 as a song-writing trio in Trondheim, Norway, consisting of Tor Erik Hermansen, Mikkel Storleer Eriksen, and Hallgeir Rustan (born 11 April 1966). When they first met, Hermansen was a talent scout for the Norwegian branch of the record label Warner Music Group, Eriksen owned a studio, and Rustan was a mechanical engineer before becoming involved in music. One of their first successful productions was with Norwegian R&B singer Noora Noor. Her first album "Curious" was produced in their Trondheim studio. Noora Noor was signed to the Norwegian branch of the record label Warner Music Group. "Need You", her main hit from this album, was released throughout Europe and gave Stargate attention from the UK music industry. While in Norway, they ventured into the British market, mostly writing songs for R&B-pop performers. At this time they called the team Stargate, a name specifically established for their projects in the United Kingdom.
The team's initial successes was in the British market. Stargate's first international success came with British pop outfit S Club 7, whose 1999 single "S Club Party" reached No. 2 in Australia and No. 1 in New Zealand. This success was followed with another British pop group, Hear'Say's single "The Way to Your Love", which peaked at No. 1 in the United Kingdom in 2001. The team has also produced many Top 10 hits in the United Kingdom for acts such as Blue, Mis-Teeq and Atomic Kitten, and worked with European acts Javine, Shola Ama, Five, and Samantha Mumba.
The team had been listening to American hits and "trying to measure up". They remixed American hip-hop and R&B songs, adding layers of melody to suit the European radio audience. In the wake of their early successes, the team had to choose whether to remain in Norway or move to pursue their goals: "We knew that to make the records we really wanted to make, we had to go to America." Hermansen and Eriksen chose to produce records in the United States, while Rustan preferred to remain a producer in Norway because he did not want to leave his family behind.
In 2001, Stargate produced and co-wrote songs for American pop singer Mikaila's self-titled debut album. "So in Love With Two", a track from the album, had reached No. 25 on the US Billboard Hot 100, becoming one of the team's earliest co-written singles that appeared on the US charts. It was followed three years later with Mis-Teeq's "Scandalous", which peaked at No. 35 on the Hot 100 and No. 2 in the United Kingdom.
In the spring of 2005, Eriksen and Hermansen settled in New York. Initially, their work was slow until they met singer-songwriter Ne-Yo in a hallway at Sony Music Studios in New York. Ne-Yo, who had been working on his debut album, In My Own Words, decided to collaborate with the team, aware that Stargate produced R&B records. After listening to each other's music, a songwriting session ensued and spawned in its second day the song "So Sick", which later topped the Billboard Hot 100 and ushered Stargate into American pop songwriting.