Elvenking was formed in October 1997 by two guitarist friends, Aydan and Jarpen, both sharing a passion for metal music and folklore. Although they were soon joined by Sargon as bassist, the young band faced many issues with its line-up that prevented them from progressing. In March 1998, Damnagoras joined the band as a lead singer, and was followed by the arrival of the drummer Zender in September. It was only then that the band found a definite stability.

The primary goal of Elvenking is to create a fusion of power metal and folk music. After gaining experience through many shows, the band decided to record a promotional album, To Oak Woods Bestowed, in 2000. Damnagoras performed both lead vocals and bass for the recording and subsequent concerts as Sargon previously left the band. The demo was successful enough to allow Elvenking to sign a contract with German label AFM Records.

Soon after, Gorlan, a friend of Aydan and Jarpen, fully joined as a bassist; before he appeared as a session player.

The first full-length album Heathenreel was recorded at New Sin Audio Design by Luigi Stefanini and mixed at Fredman Studios by Fredrik Nordstrom. The cover artwork was created by Travis Smith and the band logo was designed by J.P. Fournier, who also designed covers for Avantasia and Immortal. The album was released on July 23, 2001 and received praise from metal critics around the world. Elvenking then toured around Europe at festivals with better known bands like Blind Guardian, Gamma Ray, Edguy and Virgin Steele.

In August 2002 singer Damnagoras took leave from the band due to health concerns. Elvenking then recruited a new vocalist, Kleid, who revitalized the spirit of folk music within the band. Elyghen, a violinist and keyboard player, joined soon after. The shift in the line-up led to their second album, Wyrd, recorded at Gernhart studios in Siegburg with Martin Buchwalter, and mixed & mastered at House of music studios with Achim Kolher and released on April 19, 2004.

In late 2004 Damnagoras returned, taking the place of Kleid, and Elvenking began working on their third album, The Winter Wake.

On February 4, 2005, founding guitarist Jarpen left Elvenking. Aydan commented:

"Jarpen didn't feel comfortable playing Elvenking's music anymore having lost passion in this kind of stuff. It was a long time he was talking with us about and when Damna was back in, knowing the direction we wanted to go, he told us his willing to leave. We have tried to convince him to give it a try but it didn't worked out. It's a really sad thing because Jarpen was one of the founding members and we have created all this from the beginning together, but on the other hand being friends before musicians we know that this is what Jarpen wanted and we totally respect his decision. We will miss you, friend!"

The Winter Wake was released and premiered live on March 11, 2006 in Pordenone, Italy.

On November 3, 2006, a new album was announced to be in the works according to the official website. It was released on September 14, 2007. The album is named The Scythe and it's a conceptual album about death.

On April 14, 2008, the band announced that they were beginning work on the next album and that it would be a "totally acoustic album". In a later post the band explained that while they viewed this new album as a chance to explore their folk influences it would also be a chance for them to experiment in new areas as well. It was also added that they already had some material written for a "heavy" album however this album would wait until after the acoustic album was released.

On January 14, 2009 they announced a new guitarist on the website, Raffaello "Rafahel" Indri. He has been playing gigs with the band for the past year, and is now an official member of the band.

On September 29, 2009 they announced Lethien to be their new live violin player and to take Elyghen's place in the rehearsal room until his return to Italy.

On February 9, 2010 it was announced that Dennis Ward will produce Elvenking's new album, with Mat Sinner (Sinner, Primal Fear) also taking the role of executive producer. The recordings started on March 20. The album, called Red Silent Tides, was released on September 17 in Europe, and November 9 in North America.