There is evidence of advanced stone tools characteristic of Neanderthals in the Middle Paleolithic (about 40,000 years ago.) It is debatable whether the Neanderthals ever really "died out". There seems to be evidence of interbreeding, which would indicate that we and they are of the same species.
"Most recently, DNA studies suggest that Neanderthals and Early Modern Humans were not related, but had a common ancestor about 550,000 years ago."
"Specimens attributed to Homo heidelbergensis range from 600,000 to 350,000 years in age, making it considerably earlier than the material assigned to Germany's other, more famous caveman, Homo neanderthalensis. "
Although H. sapiens sapiens/neanderthalensis and H. heidelbergensis probably have a common ancestor at some time in the past, there is no evidence that one did 'branch off'' from the other.