Look out for my article on Early Military Records, which is published in Your Family Tree magazine (issue 132, August 2013). The article, which is tied in to the 500th anniversary of the Battle of Flodden Field - the last battle in which a British king fell - looks in depth at the ways in which you can trace your military ancestors back through the early modern and medieval periods.
A surprising number of early military records survive. Before the mid-sixteenth century, there was no standing army and, instead, troops would be raised for a particular campaign. Being prepared for military action was a fact of life in the medieval period, with the feudal system requiring guarantees of knight's service in return for the use of land.