Entwine was never originally assembled as a death metal band, Kaamos, in 1995 by guitarist and vocalist Tom Mikkola, drummer Aksu Hanttu and bassist Taipale. In 1997 they decided to change Entwine's musical style to gothic metal and rhythm guitarist and vocalist Panu Willman was shortly after added to the band's line-up. In December of that year, Entwine recorded its first demo, entitled Divine Infinity. In February of 1998 keyboard player Riitta Heikkonen joined the band.

Entwine's debut album Treasures Within Hearts was released it in September of 1999. In April of 2000 both Willman and Taipale left the band, with the latter being replaced by Joni Miettinen. Vocalist Mika Tauriainen was added to the band on the following month.

The band's next album Gone was released in April of 2001. It received the award of "Album of the Month" from German magazine Hammer and the song "New Dawn" entered the "Finnish Single Charts" in one of the top ten positions.

Jaani Kähkönen joined the band as a live session guitarist in late 2001, but soon became a permanent member of Entwine. In early 2002 the band recorded their third album, Time of Despair, which was produced by Anssi Kippo. Entwine then toured Europe with Theatre of Tragedy and Ram-Zet to promote this release.

In 2003 Entwine recorded their fourth album, DiEversity, released in March of 2004. This albums showed an evolution on their sound, abandoning some of the band's gothic roots and opting for a heavier style.

Entwine released in August of 2005 an EP containing five tracks, entitled Sliver.

In August 2006 Entwine released their fifth album entitled 'Fatal Design' and toured in Europe with German gothic rock band Zeraphine.

On December 8 2006, keyboardist Riitta Heikkonen announced her departure from the band citing personal reasons. No replacement is planned. Blabbermouth

On May 3rd, 2008, Entwine announced that they have begun working on their sixth studio album which will be produced by Hiili Hiilesmaa (HIM, Apocalyptica, Sentenced), and recorded over the summer. Album will be released on January 14th, 2009.Spinefarm The title is Painstained. Blabbermouth

The upcoming album Painstained has been pushed back to weeks to the new date January 28th, 2009.