Navigation is a crucial capability for all types of manned or unmanned vehicles. However, vehicle navigation in underwater environments still remains a challenging problem since GPS signals for position fixes are not available in the water. Terrain-referenced underwater navigation is an alternative navigation technique that utilizes geometric information of the subsea terrain to correct drift errors due to dead-reckoning or inertial navigation. Terrain-referenced navigation requires the description of an undulating terrain surface as a mathematical function or table, which often leads to a highly nonlinear estimation problem. Recently, PFs (Particle Filters), which do not require any restrictive assumptions about the system dynamics and uncertainty distributions, have been widely used for nonlinear filtering applications. However, PF has considerable computational requirements which used to limit its applicability to problems of relatively low state dimensions. This study proposes the use of a Rao-Blackwellized particle filter that is computationally more efficient than the standard PF for terrain-referenced underwater navigation involving a moderate number of states, and its performance is compared with that of the extended Kalman filter algorithm. The validity and feasibility of the proposed algorithm is demonstrated through numerical simulations.