Terrain-referenced navigation (TRN) is a technique which utilizes bathymetry information to correct drift errors from dead-reckoning or inertial navigation. This approach is available as a navigation algorithm in underwater environments where GPS is not available. TRN requires describing an undulating terrain surface as a mathematical function or table, which leads to a highly nonlinear estimation problem. Recently, for nonlinear filtering, particle filters (PF) which have no restrictive assumptions about the system dynamics and uncertainty distributions have been used. However, the use of the PF requires considerable computational resources in order to obtain reasonably good results. This study proposes the use of a Rao-Blackwellized particle filter (RBPF) that can greatly improve the filter’s computational efficiency. The validity and feasibility of the proposed algorithm is demonstrated through numerical simulations in an actual seafloor topography.