At some point in history someone must have come up with the novel idea to put a second floor directly on top of the first to maximize the area a house took up, so when and where was it?
It is somewhat disputed what houses in Mesopotamia looked like, but the consensus is that at least some of them had two stories, I believe. The earliest archaeologists certainly believed this, and I think it was Wooley who drew up plans for houses in Ur with a wooden upper story that looked suspiciously like the hotel he stayed in.
Since then, it has been a matter of a bit of dispute, but I was always taught that palaces and larger buildings at least had more than one story.