Underwater localization is important for underwater mobile robots to autonomously investigate marine resources. A method using inertial navigation system is a conventional underwater localization. However, it requires expensive sensors. In this study, we propose a laser odometry to localize an underwater walking robot. In the laser odometry using optical sensors, motion is estimated by tracking laser speckle patterns. However, measurement error increases when the sensor is tilted. In this paper, we describe the overview of our walking robot with the sensor, the principle of laser odometry, and the experimental results of investigating measurement accuracy, in which the accuracy is improved by considering a tilt angle.