La composición del álbum comenzó a finales de 2005, y la grabación duró la mitad dek 2006.^[1]​ En cuanto a su inspiración, el grupo citó libros y momentos importantes de su vida personal, sobre todo el acto de tomar decisiones. Sobre ciertas canciones, como «Our Solemn Hour», la vocalista Sharon den Adel escribió que «también se sacrifica a la gente por la guerra y no aprendemos de ello».^[1]​ Sobre su segundo sencillo «Frozen», den Adel dijo que «escribieron una canción sobre el abuso infantil», así que lanzaron la canción como sencillo y donaron todos los beneficios a Child Helpline International. En palabras de den Adel: «Elegimos esta organización porque está representada en 160 países y es muy fácil ponerse en contacto con ellos. Puedes enviarles un correo electrónico o llamarles. Están ahí no sólo para ayudar, sino también para escuchar, y tú puedes decidir cuánta ayuda quieres».

Como el álbum se centra en algunas de las difíciles decisiones que la gente toma a lo largo de su vida, el grupo decidió reflejar este tema representando en la portada a Lady Justice, una figura conocida por simbolizar el peso de las decisiones morales. La ilustración corrió a cargo del artista holandés Erwin Olaf.^[2]​

Todas las letras escritas por Sharon den Adel y Robert Westerholt.

Se lanzaron otras versiones del disco, principalmente con bonus tracks como el Rock Mix de "What Have You Done". La mayoría incluían la versión del álbum de dicha canción, mientras que la edición estadounidense llevaba consigo la versión del sencillo que se lanzó ahí, una versión editada parecida al "Rock Mix" original. Además, en Japón se lanzó una versión que incluía un DVD de un concierto en Tokio, más los videos musicales.

Outtakes / B-Sides

• «Blue Eyes» - 5:26 - Incluida en la EP edición limitada europeo del sencillo de «What Have You Done».
• «Sounds Of Freedom» - 4:57 - Incluida en la edición EP limitada del sencillo de «Frozen». En realidad no es un outtake, pero se la considera.
• «The Last Time» - 4:39 - Está incluida en la edición EP limitada del sencillo de «All I Need» en versión demo.

Además, se sacaron versiones demo de canciones del álbum en los sencillos:

• «Hand of Sorrow» (demo version) - Incluida en la descarga de «All I Need» en iTunes
• «Our Solemnr Hour» (demo version) - Incluida en «All I Need»
• «Frozen» (demo version) - Incluida en «All I Need»

En la etapa de este álbum. Se han llegado a estrenar los siguientes videos (ordenados cronológicamente):

• The Howling (tráiler del videojuego "Cronicles of Spellborn)"^[3]​
• What Have You Done (versión Europea)^[4]​
• What Have You Done (versión Inglesa)^[5]​
• Frozen^[6]​
• The Howling^[7]​
• What Have You Done (versión Norteamericana)^[8]​
• All I Need^[9]​
• Forgiven^[10]​

• Sharon den Adel - voz
• Robert Westerholt - guitarra eléctrica
• Ruud Jolie - guitarra acústica y eléctrica, mandolina, voz de respaldo
• Martijn Spierenburg - teclados, arreglos
• Jeroen van Veen - bajo
• Stephen van Haestregt - batería

The Heart of Everything debutó en el puesto número uno en Países Bajos, por primera vez en la banda. En el resto de Europa, el álbum tuvo buen desempeño, alcanzando el número uno también en Bélgica, Finlandia, y la lista de los 10 primeros en Alemania, Suecia, Suiza, la República Checa, Japón, Noruega, Portugal, Grecia, Francia. Y además llegó puesto número 20 en Austria, y 30 en el UK y Dinamarca. Vendió 150,000 copies en la primera semana de lanzamiento.