Если речь про государственность именно в полном современном понимании, когда неотъемлемым признаком государства является суверенитет, то это совокупно вся Западная Европа после Вестфальского мира 1648 года (постепенный процесс на протяжении второй половины XVII века). Так как именно тогда сложилась первая система международных отношений и тот самый суверенитет возник (вместе с современным понятием "государственная граница", например).
Если же подходить к вопросу чуть менее строго, то разумнее всего сказать о Риме — чего стоит само понятие гражданства (к которому после краха империи, кстати, Европа лишь в Новое время вернётся) не в плане "полноправный житель города" (как те же полисы), а с возможностью быть римлянином хоть в Британии, хоть в Испании, хоть где. Но опять же, всё это касалось только Рима, в вопросе государственности существовавшего "в вакууме".
То, что было до пика развития Рима и после его падения до 1648 года — скорее с нашей колокольни "государственные образования", "образования с признаками государственности". Но не в полной мере то, что мы понимаем под государством сейчас.