A crucial point of contention here is: what counts as a "nation-state"?
States of various forms have certainly existed and come into existence repeatedly through human history, since about ~11,000 years ago. (That said, it's an interesting question why exactly states formed; there's some reason to think it required rather unusual conditions. The book Against the Grain by James Scott tries to tackle this topic.)
On the other hand, as the video describes it, a nation state is a state with a collective identity tied to a shared language, "race", and set of borders, usually maintained by a collective mythology which imagines this shared identity has deeper roots than it actually has. (For example, Joan of Arc is an important figure in the mythos of the French nation-state; but would most people living in what is now France in the 15th century have identified themselves primarily as "French"?)
I don't know much about native American history. Do you think most native American civilisations fit this description? I can think of plenty of states which don't. Examples of states which are not nation states would include: feudal states (medieval Europe); city-states (ancient Greece); empires of conquest (the Alexandrian empire, the Mongol Khanates); and empires united by religion (the early Caliphates).