Neanderthals are supposed to have died out about 40,000 years ago. It is sometimes suggested that very small relict populations in particularly remote/cold/mountainous areas might have persisted much later, giving rise to the very ancient folklore found in so many places about giants, trolls, ogres, etc. up in the mountain caves. That may be nothing more than romantic nonsense -- there seems to be a spectacular lack of evidence other than old stories with no more foundation than today's anecdotal sightings -- but: the wooly mammoths lingered on until about 4,000 years ago, finally dying out as the Egyptians were well into the Age of the Pyramids.
Along those same lines of thought, another would be “dragons.”