(legend for the map here)

Agriculture did develop between 10000 and 5000 BC.

The earliest known wall is in Jericho and dates from the 8th millennium BC:

Pre-Pottery Neolithic A, 8350 BC to 7370 BC. Sometimes it is called Sultanian. The site is a 40,000 square metre settlement surrounded by a stone wall, with a stone tower in the centre of one wall. This is so far the oldest wall ever to be discovered, thus suggesting some kind of social organization, even if based on charisma. The town contained round mud-brick houses, yet no street planning. The 400-2000 dwellers used domesticated emmer wheat, barley and pulses and hunted wild animals.

The difference between a town and a city seems to be division of labour and organised government, and the first cities seem to date from the Bronze age (e.g., Mohenjo-Daro). But metalworking (copper) is much older than that, so apparently that didn't require or lead to complex social organisation or division of labour?

Now, to call the last 5000 to 10000 years "a particular historical phase" seems a bit much. And consider that "kings" were replaced by "republics" in various places around 500 BC. Though maybe by "kings and armies" you meant "states" (see the map above).

"It's the statue, man, The Statue."