Joakim Nilsson, Rikard Edlund (both formerly of Norrsken), Axel Sjöberg, and Truls Mörck formed Graveyard in 2006.

When Norrsken disbanded in 2000, guitarist Magnus Pelander went on to form doomy folk metal act Witchcraft and Nilsson and Edlund joined Albatross, a growly blues rock band whose lineup also included Sjöberg on drums.

Initially, they considered Albatross a hobby project, but after five years the members began taking their music more seriously and had grown dissatisfied with the direction their sound had taken.

When Albatross broke up, Nilsson and Edlund decided that for their next venture, they would head back towards their roots as musicians and songwriters.

Songs from the band's Myspace caught the ear of Tony Presedo, founder of Tee Pee Records.

On their official Facebook page, Joakim Nilsson announced that Graveyard are working on dates for a worldwide tour: "We're excited to visit new places, where we haven't been before.