The sound speed error and calibration accuracy of acoustic beacon arrays have a significant impact on the positioning accuracy of underwater navigation systems. Conventionally, beacon calibration and sound velocity error compensation are performed prior to integrated navigation, but this approach often leads to reduced calibration efficiency and renders the navigation accuracy vulnerable to variations in the underwater environment. To address these issues, a simultaneous navigation and calibration (SNAC) algorithm is proposed in this paper for underwater acoustic beacon arrays based on random positions. By treating the sound speed error, the position of the AUV, and the positions of the beacons as state variables, the algorithm performs real-time corrections to the dead-reckoning position while simultaneously estimating the sound velocity error and the positions of each beacon, leveraging the measured slant ranges from the beacons as observations. Simulation results demonstrate that the proposed SNAC algorithm can accurately estimate the sound speed error. Compared to the LS method, the proposed algorithm significantly improves the estimation accuracy of the beacon array, reducing the error from over 5.00 m to within 1.00 m. Additionally, the position estimation error of the AUV is also within 1.00 m, greatly enhancing the efficiency and accuracy of the underwater navigation system.