The startup company Fleet Cleaner has developed a mobile robot, specialized in the hull cleaning of large cargo vessels. Navigation and localization of this robot is currently performed manually. This is a difficult process that is greatly complicated during operation. This is mainly due to the availability of relative positioning sensors only, which are prone to error build-up and noise, and to the difficulty of interpreting optical underwater images in turbid water conditions. Instead, operators must rely on acoustic images from a forward-looking sonar. In the field of mobile robotics, Simultaneous Localization and Mapping (SLAM) is an often used technique to improve navigation and localization by utilizing visual information. The objective of this thesis is to develop a sonar-based SLAM framework, tailored to working environment of the Fleet Cleaner robot. The thesis scope has been restricted to the conceptual design of such a framework and the implementation of one of the subsystems, visual odometry.  A conceptual design of a SLAM system is proposed using a systematic approach. Different working principles are evaluated according to operating conditions and requirements that specify desired behavior. Analysis of operating conditions reveal the limitations of sonar imagery, such as a high signal-to-noise ratio and inhomogeneous intensity patterns. In addition, the environment is sparse, with few distinct recognizable landmarks, limiting feature-based approaches. Because of these limitations, visual odometry is essential to reduce error build-up between loop closure corrections. A Fourier-based approach to visual odometry is implemented, taking the whole image view into account instead of extracted features. By analyzing the dominant peak in the phase correlation matrix, the in-plane sonar motion between consecutive image frames can be estimated. Several image processing steps are necessary to improve peak sharpness, increasing the quality of registration. To validate the proposed method, an experiment was conducted during cleaning of the Pioneering Spirit, the world’s largest construction vessel. Under normal circumstances, visual odometry showed less error build-up in the position estimate than wheel odometry. However, outliers appear when driving near the waterline, caused by reflections and wave reverberations. Ultimately, the proposed visual odometry method improves the current positioning system and serves as a basis for an integral SLAM implementation.