This paper presents a novel method for visual-based 3D mapping of underwater cultural heritage sites through marine robotic operations. The proposed methodology addresses the three main stages of an underwater robotic mission, specifically the planning phase, the mission-time and the offline processing phase. Initially, we approach mission planning through multi-vision sensor configurations and simulations of the underwater medium's effects. Subsequently, we demonstrate a possibility for real-time 3D surface reconstruction and hole detection by using Poisson Surface Reconstruction (PSR) and the Ball Pivoting Algorithm (BPA), that allows for real-time quality assessment of the acquired data and control of the coverage of the site. Last, an offline photogrammetric workflow is discussed in terms of geometric reliability and visual appearance of the results. The presented three-steps methodological framework has been developed and tested in both simulation and real-world environments for three wreck sites in the fjord of Trondheim, Norway, introducing among others novel marine robotic technology like the articulated robot Eelume.