We describe a systematic approach to building ab initio tight-binding models and apply this to hexagonal metals Mg and Zr. Our models contain three approximations to plane-wave density functional theory (DFT): (i) we use a small basis set, (ii) we approximate self-consistency, and (iii) we approximate many-center exchange and correlation effects. We test a range of approximations for many-center exchange-correlation and self-consistency to gauge the accuracy of each in isolation. This systematic approach also allows us to combine multiple approximations in the optimal manner for our final tight-binding models. Furthermore, the breakdown of errors into those from individual approximations is expected to be a useful guide for which approximations to include in other tight-binding models. We attempt to correct any remaining errors in our models by fitting a pair potential. Our final tight-binding model for Mg shows excellent agreement with plane-wave results for a wide range of properties (e.g., errors below 10% for self-interstitial formation energies and below 3% for equilibrium volumes) and is expected to be highly transferable due to the minimal amount of fitting. Calculations with our Zr model also show good agreement with plane-wave results (e.g., errors below 2% for equilibrium volumes) except for properties where self-consistency is important, such as self-interstitial formation energies. However, for these properties we are able to generate a tight-binding model which shows excellent agreement with non-self-consistent DFT with a small basis set (i.e., many-center effects are captured accurately by our approximations). As we understand the source of remaining errors in our Zr model we are able to outline the methods required to build upon it to describe the remaining properties with greater accuracy.