Well defined states with foreign policies, governing systems, monopolies on the legitimate use of force, regulations, taxation etc etc have existed for thousands of years... we can go back to egypt vs kush vs the hittes. I think those were probably 'states'.
The greek city-states were DEFINITELY `states'.
States have existed for a while. And I think some of these states had well defined borders meant to interdict and restrict human movement. The roman empire definitely was pretty pre-occupied with border control/walls-see hadrian's wall.
The idea that states should have the consent of the governed or reflect a relatively homogeneous ethnic block with ties of common culture/history is more modern. which is probably what you are thinking of when you say `nation state'.
On the contrary, the idea of "each tribe on its own territory, with perpetual low-intensity border disputes between all neighbors" is literally the oldest possible social arrangement.
How does a movement of a person though a territory hurts anyone or their nose?
Also, "nation states" are an extremely recent development.