Luego se uniría el teclista estadounidense Jonah Weingarten, y el vocalista, también de procedencia norteamericana, Lance King, ex-Balance of Power.

[1]​ En febrero de 2006, la banda lanzó su segundo trabajo, Legend of the Bone Carver, un disco conceptual que fue muy bien recibido por los fanáticos.

En noviembre de 2006, se anunció que el vocalista Lance King dejaría la agrupación, por lo que Matt Barlow (ex-Iced Earth) volvió a la escena del metal, tomando el lugar de King.

Poco tiempo después el sitio oficial de Pyramaze indicaba que Barlow finalizaría la grabación del nuevo material de la banda, llamado Immortal, y luego volvería a trabajar junto a Iced Earth.

[1]​ Entre 2011 y 2015 la banda entró en un periodo de inactividad, hasta que el vocalista Terje Haroy ingresó en la formación para grabar el álbum Disciples of the Sun.