Aiming at the problem of Autonomous Underwater Vehicles (AUVs) cooperative navigation and positioning in unknown underwater environment by using the relative observation information between AUVs, the AUVs parallel cooperative navigation positioning algorithm based on factor graph is proposed in this paper. Firstly, the mathematical model of AUVs parallel cooperative navigation system is constructed. Secondly, the factor graph model of AUVs parallel cooperative navigation system is constructed by the factor graph theory, and the local navigation information of each AUV and the relative observation information between AUVs are split into each AUV platform node. Finally, the optimal estimation of navigation state of each AUV can be obtained according to the passing and updating of messages in the factor graph model of the AUVs parallel cooperative navigation system. Simulation results show that the proposed algorithm can use the relative observation information between AUVs to delay the divergence of navigation positioning error effectively.