We investigate the atomic structure of fivefold surface of icosahedral (i-) Al-Cu-Fe quasicrystal using scanning tunneling microscopy (STM) under ultra high vacuum (UHV). Annealing the sputtered surface at appropriate temperature produces a step-terrace structure on the surface. Our STM analysis indicates that the terraces are separated with primarily two stepheights in the ratio of t=5+1 /2 , a characteristic ratio in quasiperiodic structures. The measurements agree with the results from dynamical low energy electron diffraction (LEED) calculations. The spatial distribution of stepheights along the fivefold axis does not follow the quasiperiodic Fibonacci sequence. The existence of such stacking defects in the bulk structure is confirmed with the screw dislocations often observed in the STM scans. The first atomic resolution STM images on this type of material are obtained. The flat terraces are dominated with "ten-petal flower-like" motif, locally arranged with fivefold symmetry. Similar structural features can be identified in the atomically-dense planes generated from one of the available bulk structure models. Based on these results, we conclude that the fivefold i-AlCuFe surface corresponds to a two-dimensional cut of the bulk material. After examining the clean surface, we investigate the nucleation and growth of aluminium metallic thin films on the quasicrystalline i-Al-Cu-Fe fivefold surface. Upon deposition at room temperature, aluminium adatoms nucleate as pentagonal "starfish" with uniform size and in the same orientation. The same structure features are observed for different fluxes at low coverages. Based on the experimental results and the available bulk structure model, we identify the specific nucleation sites on the substrate and develop a model for the formation of the pentagonal starfish.