Since when does Valhalla exist in Norse mythology ? Like (almost) all Indo-Europeans the Vikings believed in a cycle of life, death and rebirth. Valhalla contradicts this fundamental content of Norse mythology a bit. So was Valhalla introduced in a late 'stratum' of mythology or how did the concept of Valhalla develop ?
No one knows specifically when Valhalla became a part of Norse mythology, but it was -as far as we know- first recorded in the stanzas of a 10th century poem commemorating the Eric Bloodaxe known as Eiríksmál. This skaldic poem as compiled in Fagrskinna, a latter work written in 1220 that is know as one of the kings' sagas, a series of old Norse tales and the story that codified Valhalla for many Norse and non-Norse peoples.