When was the term "Nationality" first came into use? How did ancient civilizations refer to themselves? When we refer to Ancient Civilizations, did they consider themselves a nation in the modern sense and applied this to other civilizations? Saying he is of Roman, Persian, Egyptian Nationality? or was it only a reference to the cities people came from? How and when did the term nationality develop to be is current form?
This is not a complete answer because your question is actually a huge topic with many possible approaches.
Birth is ethnicity
My personal view on this is that, long ago, at a time when the nomadic way of life was the rule, nations did not relate to geographical origin but rather to birth.
The etymology of various IE languages is very clear on this:
In Latin. Your clan name is your gens, later your "family name" (nomen) and conveys the notion of ascendancy in various cognates some of which have found their way in English (e.g. genus). The word nation itself is from Latin natio and goes back to *gnascor with an initial g : "to be born" (Meillet).
In Greek the same holds true with γένος (race) which comes from γίγνομαι "to be born".
Old English is (and more generally all German languages are) also very clear: cyning (King, see German König) is the leader of the kin (family "cynn"). See also German Kind (child).
All these considerations were still applicable even after tribes had settled down (owing to the mastering of agriculture and metallurgy) because the geographical origin was until recently a reliable indication of your ethnicity.
Us and them
Overall it seems that the "us and them" way of seeing things was very common. I was recently reading this Wikipedia article about Samnium and there was an interesting conjecture, developed by Pokorny, about the relation between various Indo European tribe names: Suebi, Semnones, Suiones, Senones, Serbs, Sabelli, Sabini, etc., as well as a large number of kinship terms. The general concept is "our own kith and kin,". It also yields English self, German selbst, etc...
Nations identified by commonalities
In antiquity, City-states could be grouped in nations, mostly through their common language.
Greek cities, despite their constant rivalries, had a strong conviction of their commonalities with each other (κοινή, κοινός = common) and of their differences with other nations mostly based on language (βάρβαρος who speak gobbledygook).
Even Phoenicians or Etruscans who were could be considered as a mosaic of city states saw themselves as nations and had their own endonyms (Rasena/Rasna "the men", Kenaani/Kinaani "Canaanites").
Of course the differences between endonyms and exoyms sometimes blur the picture, but this is yet another fascinating topic.
"Nationalism" as a term in its modern definition Regularly being referred to as an author of remarkable influence on the terms nationality and nationalism in their modern recipation is Johann Gottfried Herder (1744-1803). In his work Ideas for the Philosophy of History of Humanity (1784–91), he is at least one of the first to claim that human societies naturally tends to form nations as a basis for their social framework. Like other german philosophers, he implies that the founding of modern national states is the logical result of societies defining themselves on the basis of a common cultural history, language, and territorium. In order to develop and identify their human subjectivity in completion, people would have to be amongst their own kind, which on the other hand would allow diversiveness and individuality to emerge from society without limitation.
Context of german delay German approaches to define a progressive nationalism was highly motivated by the advanced progress of france and england in building modern states with effective economies and governments. Not being able to overcome the stagnant feudalistic conditions in the many german microstates, the originally democratic ideals of the national movements quickly transformed to an aggressive and exclusive ethno-nationalism, which is seen as a german speciality by many.
Modern nations necessitated by enlightenment and industrial revolution Probably the most influent motivation for building states implementing modern nationalism as we know it was the dramatic change of the means of production and the rise of the bourgeois class. Impelled by the natural-law-theories of thinkers like Hobbes and Locke, which provided arguments for a reliable, strong, centralistic state that could guarantee for properties of the bourgeois agenda like private property, commitment to legal contracts, and defending of the newly introduced human rights.
The revolutions in Great Britain and France were the opportunity to constitute modern national states in Europe that put an end on their predecessors's regiments of monarchy and absolutism, which couldn't realize the political and social unity which the (democratic) nationalism with its equality amongst men (like in 'male') and construed cultural heritage/identity could provide.
Edit: "Nationalism" as opposed to the nation in traditional meaning Ancient civilized societies usually meant identification with an autonomous city-state or a monarch. Given that modern nationalism and enforcing movements were an outcome of a new view on history and revolutionized forms of production, trade and exploitation, it seems legit that even though the term "nation" had been used before, the framework it referred to to be understood as being distinct from what became its meaning in the 18th and 19th century.