A mechanism of the nucleation and growth of palladium by electrochemical deposition on dc magnetron sputtered polycrystalline TiN thin films was proposed and effects of the microstructure of substrates were investigated. Field-emission scanning electron microscopy results showed that the nucleation of palladium and the number density of palladium nuclei are determined in the early stage of electrochemical deposition of palladium on TiN films. Plan-view transmission electron microscopy images of electrochemically nucleated palladium on TiN films for 5 s showed that the palladium nuclei were mainly formed on the grain boundaries of polycrystalline TiN thin films. These results mean that the microstructure of the substrate plays an important role in the electrochemical deposition of palladium, and the grain refinement of the substrate is thought to be an attractive method of acquiring high-quality films in electrochemical deposition.