It's fun to think about which modern games could have existed in the middle ages or antiquity.
Component complexity is probably the biggest limiting factor. Some components would have been very difficult or impossible to produce. The available printing technologies is a major one. Depending on how far we go back easily shuffleable cards are probably out and cards with lots of text or complex symbology are almost certainly out. So are fancy boards. Simpler boards (chess or go grids, hex) are fine. Meeples, dice, coins, tokens, bags, cups are easy.
Rules complexity might be another factor since it would be more difficult to record and reproduce very complex rules. Some kind of thematic connection woudn't hurt either. I guess you could try to explain Star Realms as heavenly chariots :)
Abstracts are a category that works well since we have a bunch of examples of those actually existing. Simple dice games, bidding games, certain drafting games should work as well.
Some specific examples of games I like to imagine existing in the past are War Chest, Onitama and Azul. Thematically they would fit well, simple rules, manageable components.
I wonder which of the more complex euros could have worked. Perhaps a simpler version of Castles of Burgundy? Fewer building types to keep component and rules complexity under control. Or maybe something like Ra.