This study is focused on a novel approach to perform underwater robot localization using sonar sensors. The approach is divided in three main steps. First, the sonar data is used to build probabilistic point clouds. Second, these point clouds are registered and a pose graph is constructed. Finally, the pose graph is optimized and a globally consistent map is built. The experimental results evaluate the proposal using real data gathered by an Autonomous Underwater Vehicle.