The following paper presents results from a novel solution for improving the navigation of an Autonomous Underwater Vehicle (AUV) using a side-scan sonar. It is derived from a system that has been developed to produce high quality mosaics using a Doppler Velocity Log (DVL), a tri-axial compass and a side-scan sonar. The system has been extended by incorporating a Concurrent Mapping and Localization (CML) algorithm. The CML tool chosen is the stochastic map. This is a proven tool for navigating in unknown environments. It can be used as a substitute for common absolute sensors, such as GPS or acoustic baseline systems, or it can work with them. The system concurrently builds a map of the environment using observations of landmarks extracted from side-scan sonar and uses that map an the dead-reckoning to create and estimate of the AUV's location.