The nucleation of Pb clusters on the five-fold Al-Pd-Mn quasicrystal surface has been investigated using scanning tunneling microscopy (STM) and ab initio calculations based on density-functional theory (DFT). In the submonolayer regime, Pb atoms are highly mobile and adsorb preferentially within equatorially truncated pseudo-Mackay clusters present at the surface. The decoration of these unique adsorption sites leads to the formation of five-fold islands dubbed “starfish” and eventually to a quasiperiodic Pb monolayer. From a comparison of measured and calculated STM images it is concluded that most starfish clusters on all terraces are composed of ten Pb adatoms. A model of the structure of the starfish cluster has been proposed. Our total-energy calculations confirm its stability. The experimentally measured height profile of the starfish cluster is also reproduced by the DFT calculations.