This question is exceptionally problematic--not because of the nature of the question at all, but because of the nature of the word "state"/"nation state"/etc. among various anthropological circles.

The first solid study of the development of the state is Elman Service's Origins of the State and Civilization. Published in the 60s, Service espoused an evolutionary model of statehood, suggesting that states evolves directly from lesser developed social structures like "Big Man" kin groups. This is problematic because no society develops strictly along evolutionary lines. Throughout his book, he discusses each of 6 (if I remember correctly) pristine, primary states in various locales throughout the globe. The oldest, however, seem to be either in East Asia and/or Mesopotamia (e.g., Sumeria, Babylon, Akkad, etc.).

Norman Yoffee's highlights an important thought in his Myths of the Archaic State -- noting that "it doesn't much matter what we call things, as long as we explain clearly what we mean, and as long as our categories further research, rather than force data into analytical blocks that are self-fulfilling prophecies." (p. 1).

You see, the problem with much scholarship surrounding early state formation (and all the more so surrounding so-called "pristine" or "primary" states like Egypt or Mesopotamia) is that too often, the definition of 'state' has driven the interpretation of the data, rather than the data driving the descriptive conclusions.

Yoffee, however, seems to suggest that the earliest state type social groups were in ancient Mesopotamia. Of course, he also spends a decent amount of time discussing origins of the state and civilization in East Asia (namely, China)

Say that a state is defined as a compulsory institution, whose rules are backed by violence. When was the first of these types of institutions?