In recent years alternative navigation system such as a DBRN (Data-Base Referenced Navigation) system using geophysical information is getting attention in the military navigation systems in advanced countries. Specifically TRN (Terrain Referenced Navigation) algorithm research is important because TRN system is a practical DBRN application in South Korea at present time. This paper presents an integrated navigation algorithm that combines a linear profile-based TRN and INS (Inertial Navigation System). We propose a correlation analysis method between TRN performance and terrain roughness index. Then we propose a conditional position update scheme that utilizes the position output of the conventional linear profile type TRN depending on the terrain roughness index. Performance of the proposed algorithm is verified through Monte Carlo computer simulations using the actual terrain database. The results show that the TRN/INS integrated algorithm, even when the initial INS error is present, overcomes the shortcomings of linear profile-based TRN and improves navigation performance.