https://en.wikipedia.org/wiki/List_of_oldest_continuously_in... lists several cities already established (with walls) around 3000 BC. Why they would not be inhabitated millenia before? Just because we don't have written records?

Mostly because they hadn't invented agriculture, a less-than-10k-years-old development.

The city of Abu Herey was destroyed 10'800 BC, almost three millenia before the timeframe you just stated for the first cities.

Do you mean this site?

https://en.wikipedia.org/wiki/Tell_Abu_Hureyra

It's a unique site of possible early long-term hunter-gatherer settlement right in the middle of one of the regions in which agriculture was first developed. It also happens to be one of the first agricultural sites! The pre-agricultural populations we're talking about are a few hundred people, which feels a little short of a city.

Abu Hureyra 1 was hardly a city - more a collection of huts.

And it's one of the earliest examples of the transition from nomadic hunter gathers to more permanent settlements.

Agriculture isn't the only way to sustain moderately-sized populations, it's just the most efficient in the short term. Semi-passive cultivation is arguably more sustainable because you don't encounter the issues of deforestation, soil depletion, and centralization of resources.

Nomadism doesn't preclude semi-permanent settlements, especially as migratory patterns retrace sites.

> Agriculture isn't the only way to sustain moderately-sized populations, it's just the most efficient in the short term. Semi-passive cultivation is arguably more sustainable

There is a theory by Jared Diamond [1] of how pre-Agricultural Jomon people of Japan were able to invent pottery 18K years ago: the wild-food rich environment of Japan, being moist, temperate, and surrounded by ocean - allowed them to have very settled lives while other hunter gatherers had to constantly move.

Outside of rate examples like this, there is little evidence that non agricultural societies reached even moderate populations.

1. https://erenow.net/common/gunsgermssteel/23.php

Semi permanent sites did exist in this timeframe. But they were much smaller in terms of population and rarely (if ever) walled cities like those which existed around 4000 BCE.

Completely agree with you that agriculture is not required to form non-permanent settlements that didn't last tens of thousands of years.

A non-permanent settlement conceivably could see continuous (non-permanent) habitation for thousands of years. If, as a semi-nomadic group, you return to the same location year after year, generation after generation, and you do so alongside a large number of nearby settlements, with whom you maintain social relationships... Well, it might not have a post office or gate, but it's a dynamic fulfills many of the requirements of a "city".

No one said it had to be a single, year-round, uninterrupted settlement. A seasonal, interrupted, settlement would be no different to an asteroid.