Electrochemical characteristics of ultra thin Pd epitaxial layers deposited electrochemically on Au(111) and Au(100) surfaces were found to be strongly dependent on the surface structure and the thickness of the Pd thin layers. The electrochemical characterizations demonstrate that the Pd/Au(111) and Pd/Au(100) surfaces behave essentially like Pd(111) and Pd(100) surfaces, respectively. Formation and reduction of oxide on the Pd sub-monolayer surfaces took place at more and less positive potentials, respectively, than those on the surfaces of the Pd multilayer. The Pd/Au(100) electrode shows a much higher electrocatalytic activity for the oxidation of formaldehyde than that at the Pd/Au(111) electrode. Furthermore, the highest activity for the electro-oxidation of formaldehyde was observed at the Pd/Au(100) electrode when the thickness of the Pd thin layers was less than a monolayer. This behavior was discussed in terms of the potential- and thickness-dependent oxide formation-reduction on the Pd thin layers.