We report on the growth of Pb thin films deposited either on the Al-rich fivefold surface of the icosahedral Al-Cu-Fe quasicrystal or on the (111) surface of fcc Al. On the quasicrystalline substrate, the diffusion length of Pb adatoms is short due to heterogeneous nucleation that enforces a quasiperiodic structure in the monolayer. On the Al(111) substrate, the mobility of Pb adatoms is high and the interaction with the substrate is flatter, leading to the formation of a (√31×√31)R8.95° higher-order commensurate structure. This moiré structure propagates up to the highest coverages investigated.