In my newest world, I've been entertaining some ideas for the history of a continent, and it came to the point where the hunter-gatherer tribes living in a desert/savanna in the center of a continent would be evicted by the military of a nearby city. This is Dark Ages-level technology for the city and stone age for the hunter-gatherers. The city is fairly big (assume a population of ~10,000), and there are probably around 20 individual bands of hunter-gatherers, each between "band" and "tribe" classification (according to Jared Diamond). I don't know much about hunter-gatherer tribe demographics, but this puts it at around 50 adults in each tribe (?), for a total, if the women fight as well, of just a thousand fighters. Would it be realistic for the hunter-gatherers to win if they were united? What if they weren't? Could they at least do enough damage to the city that it would accept their claim to the land?
The only advantage the hunter-gatherers would have is their mobility and ability to live in the wilderness. They could use this to conduct raids against undefended targets. Could they leverage that into a military win?
Maybe. A medieval city certainly depends on its outlying farmland. The hunter-gatherers might kill isolated farmers and set fire to their fields. A city may depend on trade. The hunter-gatherers may raid lightly-defended trade caravans. Since this is desert/savanna, perhaps the city also depends on aqueducts. The hunter gatherers could destroy those. It's not possible to heavily defend the aqueduct at every spot where it could be attacked.
If these raids are successful for long enough, and if the city military leaders are kind of dumb, and if the city military does not have any cavalry capable of chasing down the raiders, the hunter-gatherers might starve the city out without ever taking a real fight.