Considering the two characteristics: (1) simultaneous localization and mapping (SLAM) is a popular algorithm for autonomous underwater robot, but visual SLAM is significantly influenced by weak illumination; (2) geomagnetism-aided navigation and gravity-aided navigation are equally important methods in the field of robot navigation, but both are affected heavily by time-varying noises and terrain fluctuations; however, gravity gradient vector can avoid the influence of time-varying noises, and is less affected by terrain fluctuations. To the end, we proposes a UKF-SLAM based gravity gradient aided navigation in this paper with the following advantages: (1) the UKF-SLAM is an efficient way to avoid linearization errors compared with the EKF-SLAM; (2) it improves the accuracy of navigation system without the help of any geophysical reference map; (3) it is suitable for a robot to navigate itself under the environment of weak illumination and time-varying disturbances. Experimental results also show that our proposed method has a less localization error than the SLAM-based geomagnetic aided navigation.