Если мы говорим об истории как об учебном предмете, целью которого является формирование исторических представлений и исторического мышления, то, самое раннее, его имеет смысл вводить в 8 классе, когда детям уже по 13-14 лет. Только к этому возрасту с одной стороны уже сформированы способности выстраивать сложные логические связи, а с другой - накоплен определенный социальный опыт, без наличия которого сложно воспринимать историю не просто как набор дат, а как сложный процесс, который нельзя свести к "борьбе бобра с козлом".
Если под историей понимать в первую очередь воспитательный предмет, каковым его в основном и видят в школе, то тут можно начинать с совсем раннего возраста, хоть с 5-6 лет, если историю давать в русле "рассказов о родной истории", как художественно-воспитательных сюжетов, в которых не обязательно строгое следование фактам и определенной логике исторического процесса. В этом же возрасте можно обращаться к истории семьи, города, области, подсвечивая наиболее близкие и понятные сюжеты.
В современной же школе выбрали, как мне кажется, худший вариант - начинать учить историю с 5 класса, да еще и с самого трудного периода.