I don't have a story, but I have a setting that's been really underutilized.
We, as a species, were nomadic for hundreds of thousands of years. We had tens of thousands of years of cohabitation with other hominids, intermingling, making important and powerful discoveries, exploring, etc.
And there's no one using that for a story?
The only stories about that time that I see are about dumb cavemen or ice age migration.
These people had the same mental capacity that we have now. They had culture, rituals, trade, interesting things.