Nightingale began in 1995 as a solo goth rock project of Dan Swanö, designed to explore his brief fascination with the genre, also evident on Edge of Sanity tracks such as "Sacrificed". The first album The Breathing Shadow was recorded and mastered by Swanö alone in the space of a week at his home Unisound studio, and has been described by some as a tribute to legendary goth rock band The Sisters of Mercy, whose sound it does indeed resemble. The second album The Closing Chronicles was recorded in April 1996 with his brother Dag acting as producer and contributing some guitar parts. Unlike the first album, it is somewhat influenced by progressive rock and heavy metal, and continues the conceptual storyline that began in The Breathing Shadow to the logical conclusion of the central characters' death, as it was intended to be the last Nightingale album.

After this the band went on semi-hiatus, playing a couple of live concerts in small venues around Örebro with future permanent band member Erik Oskarsson on bass and Ari Halinoja playing the drums. The second concert, in October 1998 is remarkable because it marks one of the few times Edge of Sanity songs were performed live by Swanö, the band adding two lighter tracks to bulk out their set (Swanö scarcely performed live with Edge of Sanity, citing his inability to sustain death metal vocals for long enough).

The band returned to Unisound in April 1999 to expand upon a lost demo of the track "I Return" recorded by Dan and Dag in September 1998. 2000's I is a prequel to the first two albums, half composed by Dan and half by Dag, several of the tracks, such as "Alonely" and "Dead or Alive" being recycled by Dag from previously abandoned projects and given new lyrics (the originals being both written in Swedish and outside the conceptual storyline). For the recording of "Alive Again" in May 2002 (a sequel to the original Breathing Shadow Trilogy of "I", "The Breathing Shadow" and "The Closing Chronicles") the band was filled out with Tom Björn on drums and Erik Oskarsson returning as a permanent member. This record received the most critical acclaim yet upon its release in February 2003, partly owing to the increased exposure caused by their signing of a distribution deal with American label The End Records, and saw them play a string of live shows before travelling to Västerås in June 2004 to record Invisible, which is the band's first departure from their conceptual storyline approach, dealing with a wide array of topics from love to history. The band are currently preparing for their first major tour, after re-recording a set of tracks for a best-of album, Nightfall Overture, containing songs from their first four conceptual albums as well as an Edge of Sanity track and one new Nightingale song.

The band's latest album is White Darkness and it was released 4 June 2007.
On 2 June 2014, on their official Facebook page, the band stated "The release date for the new NG album is 10 November." The new album's title is "Retribution".