We have studied a sea navigation method relying on a digital underwater terrain map and sonar measurements. The method is applicable for both ships and underwater vessels. We have used experimental data to build an underwater map and to investigate the estimation performance. Since the problem is non-linear, due to the measurement relation, we apply a sequential Monte Carlo method, or particle filter, for the state estimation. The fundamental limitations in navigation uncertainty can be described in terms of the Cramér-Rao lower bound, which is interpreted in terms of the inertial navigation system (INS) error, the sensor accuracy and the terrain map excitation. Hence, the Cramér-Rao lower bound can be interpreted and used in design for INS systems, sensor performance or if these are given, how much terrain or depth excitation that is needed for use in positioning and navigation.