We report an ab initio study of the effect of the metal-high-k dielectric (Ru-HfO2) interface structure on the effective work function of the metal. Depending on the structure of Ru deposited on the HfO2 substrate we find a variation of similar to 0.4 eV in the effective work function of the metal. The interfacial structures determine the extent of charge transfer from the metal to the dielectric and hence, affect the nature of the interface dipole. Consequently, variability in interface structure may result in differences in the Schottky barrier height and thus affect the electrode work function.