The structure of metal clusters supported on a MgO(001) substrate is investigated by a computational approach, with the aim to locate stable structural motifs and possible transition sizes between different epitaxies. Metal-metal interactions are modeled by a second-moment approximation tight-binding potential, while metal-oxide interactions are modeled by an analytic function fitted to first-principles calculations. Global optimization techniques are used to search for the most stable structural motifs at small sizes (N < or = 200), while at larger sizes different structural motifs are compared at geometric magic numbers for clusters up to several thousand atoms. Metals studied are Ag, Au, Pd, and Pt. They are grouped according to their mismatch to the oxide substrate (lattice constant of the metal versus oxygen-oxygen distance on the surface). Ag and Au, which have a smaller mismatch with MgO, are studied in Paper I, while Pd and Pt, with a larger mismatch, are investigated in Paper II. For Ag the cube-on-cube (001) epitaxy is favored in the whole size range studied, while for Au a transition from the (001) to the (111) epitaxy is located at N=1200. The reliability of the model is discussed in the light of the available experimental data.