The present paper describes the development of geophysical navigation (GN) methods for small, affordable underwater robotic vehicles. The proposed GN methods includes a classical, bathymetric-based terrain-aided navigation (TAN) approach, a magnetic-based geophysical navigation solution (MAGNAV), and an integration of both methods (TAN-MAGNAV). Due to insufficient topographic features in the adopted test site, the classical TAN approach performed poorly in terms of positioning accuracy. To mitigate this, the complementarity of magnetic and topographic terrain information was exploited, initially using only magnetic data to estimate the vehicle position and later by fusing magnetic and altitude data. The results obtained illustrate the high potential of using magnetic data for geophysical navigation of autonomous underwater vehicles. The navigation methods described are validated in simulated trials using real magnetic, topographic, and navigation data acquired with an autonomous marine vehicle in real trials. The equipment employed in the proposed solution consists of standard navigation sensors, a sonar altimeter, and an affordable total field magnetometer.