This is an anthropological question as well as a political one. Every society has building blocks. In many places around the world this is the extended family. In some places, it is a nuclear family (although this is an exception historically and geographically). Still in other places the extended family is quite large and better referred to as a clan. A tribe is best understood as clans living in close proximity to one another with interaction. There is some blurring between the clan and the tribe. There is also an unclear distinction between tribe and nation. Each of these designations are best understood on a spectrum.
Many of the world's earliest cities started to appear as early as 9,000 years ago. Archaeologists now view some of the earliest as large villages rather than cities. The earliest were Jericho (modern day Palestine) and Catal Huyuk (in modern day Turkey). These "cities" had populations of up to 6,000 people, but they did not have the social structure to make them cities. The earliest cities that all archeologists seem to agree on are Uruk and Ur, both in ancient Sumeria. Their history can also be traced back earlier, but they reached "city status" by around 3000 b.c or 5000 b.p.
The city is an important element in the question of what a nation is. The city was the next stage in political development after the tribal village system. It was in the city that early nations consolidated their identity. Each city was independent from the next. One thing that can be certain from scripture is that God took notice of cities. A prime example is Nineveh, of whom God said "how can they not be important to me? 120,000 people live there."
In the broad sense of the word a nation is an ethnic group that shares a language, culture and geographical location. There are plenty of varying debates about when a nation is defined distinctly from another, if any of these criteria change. I wrote an article a few years back about the birth of the modern Australian nation, and the seeds of the gospel within the nation. This serves to show that new nations can be born, and that the Australian nation does differ from its roots. I would definitely differentiate between the modern Australian nation, and the some 200 Aboriginal nations that existed before 1788.
In the earliest historical sense, when individual cities rose up, they were often separate nations from other cities around them. This was not always the case, sometime a nation had more than one, in the case of Ur and Uruk, but most nations did not have multiple cities. Each nation has its own distinct identity and is entitled to it as such.