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