With recent advances in battery capacity and the development of hydrogen fuel cells, autonomous underwater vehicles (AUVs) are being used to undertake longer missions that were previously performed by manned or tethered vehicles. As a result, more advanced navigation systems are needed to maintain an accurate position over a larger operational area. The accuracy of the navigation system is critical to the quality of the data collected during survey missions and the recovery of the AUV. Many different methods for navigation in different underwater environments have been proposed in the literature. In this correspondence paper, the state of the art in navigation technologies for AUVs is investigated for theoretical and operational systems. Their suitability for use in different environments is compared and current limitations of these methods are identified. In addition, new approaches to address these current problems and areas for future research are suggested. Finally, it is concluded that only geophysically referenced methods will enable AUVs to navigate accurately over large areas and that advances in underwater feature recognition are required before these methods can be implemented in operational AUVs.