Formada em março de 2006 pelos 3 jovens: Andrews Viana (guitarra/teclado), Daniel Hantaro (teclado principal) e Thiago Marques (guitarra), recém-saídos de um projeto sem sucesso e com o objetivo inicial de montar uma banda de Hard Rock para tocar covers do Kiss e do Iron Maiden dos anos 80, pode-se dizer que a Nocturnal Elegy é uma das bandas que melhor exemplifica o fato de que a resistência de uma banda em relação às suas dificuldades (até que a mesma esteja pronta para entrar para o mundo da música), é o que a faz dela uma boa banda.

Problemas que vão desde a menoridade dos integrantes até falta de equipamentos e músicos para completá-la foram enfrentados. Um exemplo disso é o fato de que o guitarrista, Andrews (que antes era baterista) largou a bateria, juntou dinheiro para comprar uma guitarra e aprendeu a tocá-la para que a banda tivesse dois guitarristas. Assim como também fez Daniel, que aprendeu a tocar teclado apenas com o objetivo de integrar a banda.

Daniela Prata é nomeada a primeira vocalista da história da Nocturnal Elegy, mas por falta de tempo não chega a ensaiar com a banda e logo é obrigada a anunciar sua saída.

Passados alguns meses, começam a compor músicas próprias (como A day after yesterday, Beside Oneself e Nocturnal Illusion), e apesar das variadas influências (Kiss, Iron Maiden, Black Sabbath, Helloween, Judas Priest, Rolling Stones, Stratovarius, entre outras), notava-se que a banda não pertencia mais ao gênero Hard Rock como os integrantes queriam no começo, e sim ao Power/Heavy Metal.

Ainda com influências do Hard Rock e também da música clássica, durante este período, a banda gravou e divulgou pequenas prévias instrumentais de suas composições (incluindo Streets at the Midnight, que quando disponiblizada na Internet contribuiu para que mesmo como banda instrumental, a Nocturnal Elegy atingisse várias vezes o topo do ranking local do www.palcomp3.com.br). Pouco depois gravam dois tributos também instrumentais, ao X Japan e Paganini (respectivamente com as músicas Art of life? e Caprice XXV), o que lhes rendeu certo reconhecimento do público por algum tempo.

Com o novo estilo definido, entram para a banda Mateus Guimarães (baixista), Juliano Perez (baterista, indicado por Thiago que o conhecia do CAM, de onde eram alunos) e Marcelo André (vocalista). Após certo tempo, Mateus é obrigado a deixar a banda por problemas colegiais.

Mesmo sem baixista, continuam ensaiando suas composições e alguns covers do Iron Maiden, mas semanas depois são obrigados a parar as atividades temporariamente, devido a um acidente ocorrido com o tecladista (Daniel), que o deixou numa cadeira-de-roda por alguns meses.
Apesar do acidente e do desânimo dos integrantes, continuam compondo mais músicas e aperfeiçoando antigos arranjos.

No final do ano, contam com a entrada de Danillo Ribeiro (baixista) e voltam a tocar os projetos para frente após a recuperação de Daniel. Meses depois, Thiago é obrigado a deixar a banda, assim como Mateus, devido a problemas colegiais.

A banda segue contando com apenas 1 guitarrista, mas durante este período compõe 3 das mais importantes músicas do seu repertório atualmente (Flying to the Perfection, Satan Eyes e Moonlight Prowler), e ainda uma balada (Song for a friend), libertando-se em parte da antiga temática da maioria de suas letras (vida noturna e passagem do tempo), para falar de temas como: superação, descontrole, mistérios da vida e dúvidas da mente humana.
Por motivos pessoais, Danillo sai da banda no meio de 2007, o que preocupou mais uma vez a banda sobre sua sobrevivência no mundo da música.
Mesmo sob tal preocupação, a banda segue em frente com seus projetos, continuando compondo e gravando prévias de suas músicas para divulgá-las.

Assim como o Helloween, a banda resistiu à menoridade dos integrantes, às mudanças de formação e à pressão externa, e 1 mês depois contam com a entrada de Danilo Viana como segundo guitarrista, após acordo do mesmo com Ícaro Prado, que apesar de também ter feito teste para guitarrista passou como baixista 1 semana depois, ajudando na gravação das duas primeiras prévias com voz a serem postadas na Internet.

Com a banda completa, os seis garotos são convidados para tocar num festival em Nossa Senhora da Glória (interior de Sergipe), ao lado de bandas experientes, como: Blaster, Necroon, Inrisório, Grinding Souls, Darkvisions, Incinerated Clitorial Region e Maniac Frost, onde através de seu show de estréia mostram que para se fazer bom Metal a idade não importa.

Atualmente, após a super-mudança de formação no começo de 2008, onde Andrews se tornou vocalista, Ícaro guitarrista e Stuart entrou pra a banda, e com a entrada de Harry Souza como novo baterista em 2011, a mesma planeja a gravação de seu primeiro demo-single, no qual promete mostrar ao mundo uma das melhores bandas de Metal que o mesmo já viu, juntando peso, agressividade, expressão e melodia nas composições.

Trazendo músicas onde para gostar, o público não precise entender sobre o gênero nem sobre as técnicas que foram utilizadas nas melodias, o principal objetivo é produzir um tipo de música onde haja a fusão do prazer de quem toca com o prazer de quem ouve.