History is an odd one because the question will always end up being 'where does the history start?' and that's a rabbit hole, and a distraction from the main story - Nolan's mission to stop the plague doesn't really require knowledge of who built what town for example, nor the life history of every NPC he talks to on that quest.
My suggestion for creating a games history is to create a map of the land this story is taking place in. The positions of the settlements can tell a story of that settlement. Is it a settlement in the high reaches of the mountains? Why is that? Were they driven up there, or have they hidden here? Do they practive unnatural magics? How long have they been doing so? Or maybe they just like mining and have found a particularly valuable vein of minerals.
The position of a settlement on the map - where it is, how big it is or how small, suggest stories of their own that you can build on. If you've already built a story, then this becomes a little more difficult - but your map can change to fit your story, and then the history can flow from what your story requires.