I don't mean modern Westphalian states, nor do I mean states in areas where government already existed. But where did hierarchical power structures, backed with violence, start?
Not a historian, but I'm pretty confident that the answer is prehistorical (it might arguably predate humanity, if we define it as broadly as you have). /r/askanthropology might be a better place to ask.