The uncertainty, complexity, and variability of the marine environment inevitably lead to a change in the measurement error resulting in erroneous estimation of navigation information. To solve this problem, this paper proposes a novel method integrating the square-root cubature Kalman filter (SCKF) with the expectation-maximization (EM) algorithm. The proposed new SCKF (NSCKF) algorithm makes better use of the advantages of SCKF and the EM online algorithm. The performance of NSCKF is verified theoretically and evaluated by experiments. The results indicate that the proposed NSCKF algorithm can better estimate predicted error covariance and measurement noise than two other comparison methods owing to the online EM method so that the more accurate attitude estimation can be obtained by the NSCKF algorithm although the measurement error has a great variation. Moreover, the accuracy and efficiency can be guaranteed by employing the SCKF. Experimental results demonstrate that the NSCKF can provide a more stable attitude estimation in different cases of measurement errors. Therefore, the NSCKF is more suitable to be used in underwater navigation than other comparison methods because of higher accuracy, more efficiency, and better robustness.