It is recognized widely enough that a pre-state society in order to get transformed into a state must have a certain size of territory and population, a necessary degree of sociocultural complexity and an ability to produce sufficient quantities of surplus. However, sometimes cultures significantly exceed required levels of those parameters without forming states. In addition to this, we know historically and ethnographically a considerable number of stateless societies not at all inferior to the early state societies with respect to their territory, population, sociocultural and/or political complexity. So, the question is: how to classify such societies? Compared to unquestionably pre-state societies, such as, for example, simple chiefdoms, they are not only larger in size but much more complex as well. In certain sense, they can be regarded as being at the same level of sociocultural development as early-state societies. And, since both types of societies faced similar problems and solved similar tasks, I denote complex stateless societies as early state analogues. This article is an attempt to analyze such analogues and compare them with early states