A method is proposed for improving the accuracy and self-consistency of bathymetric maps built using an Autonomous Underwater Vehicle (AUV) to create precise prior maps for Terrain-Aided Navigation (TAN), when the Global Positioning System (GPS) or another precise location method is unavailable. This method consists of front-end and back-end. For the front-end, the AUV predicts the measurement of the bathymetry system through Terrain Elevation Measurement Extrapolation Estimation (TEMEE) and calculates the likelihood function using real measurements. After the final Inertial Navigation System (INS) error is obtained by communicating with sensor nodes, the process enters the back-end. A Terrain Correlation Correction Method (TCCM) and an Improved Terrain Correlation Correction Method (ITCCM) are proposed to solve the gradual distribution of the final INS error to each point on a path, and the accuracy of ITCCM was confirmed experimentally. Finally, a TAN simulation experiment was conducted to prove the importance and necessity of map correction using ITCCM. ITCCM was proven to be an effective and important method for correcting maps built using an AUV.