It goes back at least to the English Civil War.

The Journal of the House of Lords for 15 March 1642 has the earliest example I've found:

Ordered, That this House joins and agrees with the House of Commons in this Vote; and that the Lord Admiral is hereby desired, from both Houses of Parliament, that the Commander in Chief of this Summer's Fleet under his Lordship, may be the Earl of Warwicke.

Before this, in December 1587, Lord Howard of Effingham received a commission as "lieutenant-general and commander-in-chief of the navy and army prepared to the seas against Spain" to fight the Spanish Armada. However, as the source I've linked shows, his commission was in Latin, not in English. I've not found any original examples of the phrase "commander in chief" in English that go back to Elizabeth's time.

The phrase "in chief" by itself goes back to the thirteenth century. It referred to a kind of feudal land tenure, where land was held directly from the king.