This paper will present a robust extended Kalman filter (REKF) applied to the navigation of an autonomous underwater vehicle (AUV) using robust Simultaneous Localization and Mapping (SLAM) techniques. Conventional Kalman Filter methods suffer from the assumption of Gaussian noise statistics, which often lead to failures when these assumptions do not hold. Additionally, the linearization errors associated with the implementation of the standard EKF can also severely degrade the performance of the localization estimate. Currently, Stochastic Mapping provides a framework for the concurrent mapping of landmarks and localization of the vehicle with respect to the landmarks. However, the Stochastic Map is essentially an augmented EKF with the limitations thereof. This research addresses the linearization and Guassian assumption errors as they relate to the SLAM problem by proposing a new method, Robust Stochastic Mapping. The Robust Stochastic Map uses a Robust EKF (REKF) in order to address these limitations through the implementation of the bounded H ∞ norm. Simulated data are presented to illustrate the advantage of the localization using the proposed estimation procedure.