I don't quite see the distinction. The early Romans, Spartans and Athenians were clearly patriotic towards their state how was that not nationalism?
Were they nation-states?
http://www.towson.edu/polsci/ppp/sp97/realism/whatisns.htm I personally think they do meet the criteria here, or as close as anyone in their time - but I'm not convinced either way.
But what I meant was that there's a difference between believing in your cultural superiority - which would take a POD before recorded history to dilute - and every group that can call itself a nation (in the sense defined above) demanding its own state.
The idea that every nation (in the sense of every soci-cultural construct) should be its own state and being part of a larger state is wrong on principle is not a development that existed in that era.
Rome managed to rule Athens with less trouble than the 19th century Habsburgs ruled Hungary, and it wasn't that Franz Joseph was a worse emperor than the average Roman Emperor.