A theoretical investigation of electrochemical hydrogen evolution on Au(111) covered with submonolayers of Pd is presented. The size and shape of monoatomically high Pd islands formed on the Au(111) surface are determined using Monte Carlo simulations, for Pd coverages varying from 0.02 to 0.95 ML. The energetics of adsorption and desorption of hydrogen on/from different types of sites on the Pd-Au(111) surface are assessed by means of density functional theory calculations combined with thermodynamic modeling. Based on the density functional and Monte Carlo data, the hydrogen evolution activity is evaluated with a micro-kinetic model. The analysis reproduces measured Pd-coverage-dependent activities for Pd submonolayers exceeding similar to 0.15 ML and enables the relative contributions from different types of electrocatalytically active sites to be determined. Finally, the implications of surface line defects for Pd island formation and hydrogen evolution are discussed. It is argued, with support from theoretical data, that this kind of defects is likely to be responsible for a dramatic increase in activity observed experimentally [ChemPhysChem 7, 985 (2006); Electrochim. Acta 52, 5548 (2007)] at low Pd coverages.