Follow up question: Was it because it became more efficient to add stability and move up (rather than buy(?) more land sideways), or for some other reason?

The earliest that springs to mind are from the Indus Valley Civilization (c.2,500 - 1,700 BC). Evidence from Mohenjo-daro suggests a flat roof or upper story as stairs are found going up, although I suspect upper stories are found much ealier than that but don't have the same level of preservation as Mohenjo-daro. For example the Near East houses are generally mudbrick and so don't survive to particualr heights usually, and earlier excavations rarely bothered with anything other than the monumental architecture. 4th Millenium Uruk-Warka for instance I suspect would have at least occupiable flat roofs, but they simply havn't been excavated.

Earliest evidence of flat roofs go back to Çatal Hüyük in Turkey as far as I can think, A Neolithic town. Seems the houses were accessed from above via ladder. Again this is probably an issue of preservation.

Düring, B. S., & Marciniak, A. (2005). Households and communities in the central Anatolian Neolithic. Archaeological Dialogues, 12(02), 165-187. [https://openaccess.leidenuniv.nl/bitstream/handle/1887/14169/During&Marcinniak2005.pdf?sequence=2]

Wheeler, S. R. E. M. (1966). Civilization of the Indus Valley and beyond. Thames.

I can't tell you when humans started adding a second storey to buildings, but I can tell you that they existed as early as 1800 BCE (probably earlier) with the Minoans, a bronze age civilization that was a precursor to the Archaic Greeks. Here's a miniature model of a fairly typical Minoan house that you might have found in Knossos.

Their reasoning for the addition of a second storey is pretty interesting, but it definitely makes sense. Unlike the mainland Greeks, the Myceneans, the towns of Crete did not have defensive walls. Invaders could enter them only to find that looting them was a real challenge. The Minoans kept most of their belongings on the top floor, and therefore only had to defend the bottom from attackers. They used the stairs and bottom floor as a choke point. As you can see in the model, the top floor has big airy windows, while the bottom only has little slits that could be used as arrow holes. In this way, two storey houses were great defensive structures; a great incentive to build up.

Source: just took a course in Greek bronze age art and architecture. If this is insufficient I could do some digging in my text book and find something to back my info up further.

The earliest that springs to my mind is actually Canhasan in Central Anatolia during the Early Chalcolithic period. Düring argues that the the published plan of Levels 2B-2A (dated to 6000-5500 BCE) only represents the floor level and that living quarters were on the second floor (2011: 142ff). He also takes a few tentative stabs at the reason that these second stories were constructed (if you're interested):

Various reasons could be put forward for introducing two-storey buildings, but the relevance of none of them can be demonstrated. These include a scarcity of good building locations in a settlement where people wanted to live in a specific neighbourhood; matters of prestige; and the need to create non-domestic spaces that could be used for storage places or as workshops. That Canhasan I might have been a central place in a wider network of dependent smaller settlements could have been important in this development (2011: 144).

Hacilar is another site, this time in western Anatolia, that seems to have had second stories in the Early Chalcolithic period (Sagona and Zimansky 2009: 130ff). I suspect there are many more, but just the two that I could remember off the top of my head (and could find authoritative sources for).

I do not think a defensive wall has been excavated at Canhasan. But there is a city wall running around Hacilar; its function is debated, however. Some people say it's defensive, others suggest it's a containment wall for animals, still others argue it's just a boundary wall.

EDIT: Backing up even more as I go through Sagona and Zimansky's book again: It seems there may have been upper stories at Cafer Höyük at the end of the Pre-Pottery Neolithic (2009: 53) and at Ilipinar ~5700 BCE (2009: 136ff). They also mention a Neolithic village Kuracay (2009: 99) that seems to have had upper storage levels. And, as others have already said, Catalhöyük is another site to look at. I may have missed a couple in my skimming, but I hope that helps.

Sources:

• Düring, B. S. 2011. The Prehistory of Asia Minor: From Complex Hunter-Gatherers to Early Urban Societies. Cambridge: Cambridge University Press.

• Sagona, A. and P. E. Zimansky. 2009. Ancient Turkey. London: Routledge.

More of an Archaeological question, but as it happens that's my thing.

Off the top of my head, one of the oldest human permanent settlements would be Tell Abu Hureyra, which now sits at the bottom of a Dam lake due to Erdogan of Turkey and his predecessors.

Shakes Trowel with rage

Archaeologists did get a crack at it before the world-heritage-value site was destroyed, and revealed several phases.

The first stage was a hunter gatherer site with simple huts (13000 years ago, ish). A fascinating site for a number of reasons, especially the evidence for early domestication of grasses, like emmer, millet, rye and several others. The site is a strong evidence for transhumance, an existence of semi-nomadic seasonal migrations. This first site's building are easily imagined, simple huts, single storey, rounded, thatched with grasses.

The later phases (about 9500 years ago) created the "Tell" an arabic word essentially meaning "hill" don't quote me on the precision on that though. The name comes from the slow accumulation of layers and floors creating an artificial hill, this would be the earliest example of multiple storeys I can think of off the top of my head.

It would have looked something like this. Although that picture looks to be of catal hoyuk, it should give you a rough idea of how it would look.

The multiple storeys are more emergent than deliberate, and look to have been built to simpy expand space for families and storage. Surplus=civilisation after all so bigger buildings is always lovely.

Short Answer: During the Mid-Neolithic period in the southern Levant (ca. 8,500-8,000 years ago).

Long Answer: The spread of domesticated crops into the southern Levant marked the beginning of the Pre-Pottery Neolithic and one of the consequences was a rapid increase in population. Now, this was not the first time in human history that our ancestors' populations spiked, but it was an unprecedented period of mounting population density as the communities in the region built permanent towns and villages next to agricultural land. Throughout the early-middle Pre-pottery Neolithic B (PPNB) settlements like 'Ain Ghazal and Beidha developed what Ian Kuijt described as, "social crowding" (p. 93)

More buildings appear over time, larger buildings are constructed, later buildings have more internal divisions (a.k.a more separate rooms), and during the late PPNB (8500BP-8000BP) two-story buildings appear.

Dr. Kuijt interprets the changes to demographic pressure, generated by food surplus from agriculture. In other words, less nomadic societies combined with more food than they could eat right away resulted in more offspring, who survived more often, thus larger families required more space. However, since they were more or less rooted to the village, and were invested in local farm plots they didn't want to build new structures farther away so they continued to modify existing buildings. This trend persisted until the end of the PPNB around 8,000 years ago when the entire region seemed to be unable to support these larger towns and all but the largest were either abandoned, or occupied only seasonally, when it was rainy enough to farm.

Site descriptions are all found in fairly older primary publications, but Dr. Ian Kuijt probably wrote most comprehensively on the subject.

Edit: fixed a link

Not the oldest in the thread, but Dendara Temple in Egypt has a 2nd floor, as well as a basement.

I recommend the book Home by Bill Bryson