Autonomous underwater vehicles (AUVs) have been used widely in underwater environments over the last few decades. In underwater environments, positioning and navigation of AUVs are challenging due to the impossibility of radio communications and global navigation satellite system. Therefore, underwater acoustic system has been the main approach adopted to solve these challenges until now. In the traditional method, the underwater acoustic positioning system (UAPS) and underwater acoustic communication system (UACS) are mostly independent, which result in the interference and the waste of energy. In this paper, we combined the UAPS and UACS together and designed the positioning signal based on spread spectrum communication technology. It could not only solve the problem mentioned above, but also improve the positioning accuracy and locate the multiple users at the same time. However, the designed signal would result in great amount of calculation with conventional serial search algorithm for the signal processing. Hence the parallel frequency search algorithm was adopted to solve this problem. Finally, the simulative experiments were implemented and performance of the two algorithms were analyzed. It is demonstrated that the frequency search algorithm could be more effective than the serial search algorithm.