The discovery of Neanderthal remains in the same location that preserved the exceptional Denisovan DNA at last provided a very high quality Neanderthal genome, the analysis of which was published just this year. This new data allowed for several more robust analyses comparing human, Denisovan, and Neanderthal genomes. These analyses produced several noteworthy results: modern mainland Asian populations also have a small amount of Denisovan DNA; humans contributed some DNA variation to Neanderthals; Neanderthals and Denisovans interbred, with DNA variation flowing both ways; and (perhaps most interestingly) Denisovans have DNA variation that suggests they interbred with yet another archaic hominin group, possibly Homo erectus.While the palaeogenomic data indicate a split time of c. 600 Ky years for modern humans and Neandertals, it is fairly clear from other genetic evidence that there was at least some interbreeding between early moderns and Neandertals all the way up to around 50 Ky B.P. (perhaps as recently as 29 Ky, given the information from the Portuguese burial at Lagar Velho), as well as interbreeding between the newly emerging African moderns and African archaic Homo sapiens.
The news that the Denisovans have some very archaic DNA in them is not surprising. IF modern humans and Neandertals split around 600 Ky B.P., the only people running around on the landscape at that point were early archaic Homo sapiens/late Homo erectus. The salient feature of the name "archaic Homo sapiens" is that it is not a taxonomic name but rather a linguistic "catch-all." The primary reason for this is because, as I noted in my series on human origins, the earliest members of this group still have some Homo erectus characteristics, while the later ones look more modern. When these fossils, which all date to between (possibly ) 800 and 400 Ky B.P., were pulled out of the ground, researchers did not know what to call them, so they applied this "catch-all." Adding to the confusion is that some of the archaic Homo sapiens crania from Africa bear more than a passing similarity to some of the finds in Europe. All were clearly transitional but what to call them was a mystery. Researchers such as Bernard Wood, applying systematics to the problem, have suggested that these forms should be given the name Homo heidelbergensis. Such a taxon would, however, have quite a lengthy geomorphochronocline, stretching its limits, perhaps, to the breaking point. For a refresher on these fossils, you might want to read this post.
So, if the split between modern humans and Neandertals was around 600 Ky B.P., who would have been the progenitors of these groups? Modern humans don't appear on the landscape until between 160 and 190Ky B.P. Neandertals don't appear until maybe 300 Ky B.P. Here is one possible scenario. Sometime prior to 600k B.P., there was a migration out of Africa by one or more groups of archaic Homo sapiens/late Homo erectus. This explains the similarities between the Petralona and African Kabwe crania, as well as that of the Gran Dolina remains and the African Bodo cranium. In Africa, the archaics went about their business being archaic until around 200 ky B.P., when the modern genome began to arise (in response to what?). In Europe, over time, in the face of not one but two ice ages (The Riss and Würm), one group evolved into the Neandertals, who's remains are found in Europe, the Levant, northern Iraq and very western Russia. Populations in the two areas would have, depending on the level of gene flow in the circum-Mediterranean area, become genetically isolated.
Now here is the really odd thing. When these groups reunited, so to speak, they discovered that, not only was there an attraction, they were still genetically compatible after some 500 thousand years apart—to a point. Even though they actually produced viable offspring (and the presence of Neandertal genes in modern humans demonstrates that they were), because the Neandertal and modern human genomes were "optimized" if you will, eventually over time, hybrid depression would likely have ensued, reducing the fitness of the hybrid offspring. This may account for the ultimate demise of the Neandertals, who had a genome that, with the warming at the end of the early Würm stadial, was likely undergoing negative selection pressure. If, in fact, there was a swamping of the Neandertal genome by arriving moderns through the gates of Europe, this would have sped up the process.
This scenario is bare bones at best but explains much of the fossil data. It leaves aside the hotly contested notion of whether or not Neandertals were a separate species from the early moderns and, with them, reflected a syngameon, or whether, as Milford Wolpoff contends, they reflect a widely polytypic species that interbred at the peripheries. That is for another day.