Metal nanostructures are, nowadays, extensively used in applications such as catalysis, electronics, sensing, optoelectronics and others. These applications require the possibility to design and fabricate metal nanostructures directly on functional substrates, with specifically controlled shapes, sizes, structures and reduced costs. A promising route towards the controlled fabrication of surface-supported metal nanostructures is the processing of substrate-deposited thin metal films by fast and ultrafast pulsed lasers. In fact, the processes occurring for laser-irradiated metal films (melting, ablation, deformation) can be exploited and controlled on the nanoscale to produce metal nanostructures with the desired shape, size, and surface order. The present paper aims to overview the results concerning the use of fast and ultrafast laser-based fabrication methodologies to obtain metal nanostructures on surfaces from the processing of deposited metal films. The paper aims to focus on the correlation between the process parameter, physical parameters and the morphological/structural properties of the obtained nanostructures. We begin with a review of the basic concepts on the laser-metal films interaction to clarify the main laser, metal film, and substrate parameters governing the metal film evolution under the laser irradiation. The review then aims to provide a comprehensive schematization of some notable classes of metal nanostructures which can be fabricated and establishes general frameworks connecting the processes parameters to the characteristics of the nanostructures. To simplify the discussion, the laser types under considerations are classified into three classes on the basis of the range of the pulse duration: nanosecond-, picosecond-, femtosecond-pulsed lasers. These lasers induce different structuring mechanisms for an irradiated metal film. By discussing these mechanisms, the basic formation processes of micro- and nano-structures is illustrated and justified. A short discussion on the notable applications for the produced metal nanostructures is carried out so as to outline the strengths of the laser-based fabrication processes. Finally, the review shows the innovative contributions that can be proposed in this research field by illustrating the challenges and perspectives.