We have investigated the adsorption of Pb atoms on the (100) surface of an orthorhombic Al13Co4 crystal at 300 and 573 K substrate temperatures. This complex metallic alloy is an approximant to the decagonal Al-Ni-Co quasicrystal. At submonolayer coverage and at 300 K, Pb adatoms remain highly mobile and adsorb preferentially within the hollow site situated in between adjacent Al pentagonal clusters present at the surface. These experimental findings are supported by ab initio calculations based on density functional theory (DFT). For both temperature regimes, Pb adsorption leads to the formation of pseudomorphic monolayers above which the high adsorbate mobility prohibits the growth of additional layers. For the high-temperature deposition, we propose a structural model for the Pb film and discuss its relationship with the underneath substrate.