Nowadays it is common for militaries to think about past experiences when planning. For example, the Soviet army would study their military history in WW2 in planning during the Cold War, while the US studied German experiences. But when is the first recorded instance of history factored into planning? What past battles were studied, and what was concluded about them?
I don't know about "military leaders studying military history," but one of the oldest military treatises that I know of is the Liutao written by Lu Shang, a Zhou dynasty general sometime around 1000 BC. He wrote this treaty upon reflecting on his defeat of the Shang dynasty forces during the overthrow of the Shang dynasty. It discusses both civil and military affairs, however, so it is not quite "military history," but it is known today as one of the great Chinese military works alongside the more famous Art of War.
At the Battle of Leuctra (371 BCE), the Theban general Epaminondas arranged his troops in a way that was specifically designed to counteract the way his enemies (the Spartans) always arranged theirs.
He didn't need to study Spartan history to know that, though. The Spartans' usual order of battle would have been common knowledge, because that's how Greeks in general usually did it.