Positioning accuracy of vessel celestial navigation is limited by the low measurement accuracy of celestial altitude. For solving this problem, a novel method of celestial altitude determination is proposed. Refraction angles are obtained by two star sensors using a star pattern recognition method; the celestial altitudes are calculated accurately from the refraction angles according to the atmospheric refraction model. Simulation results show that the final vessel positioning accuracy can be better than 23 m under the conditions that the star sensor accuracy is 1″ and the observation altitude is about 6°. The effect of measurement accuracy of refraction angle, observation celestial heights and atmospheric refraction model accuracy on positioning accuracy is analyzed.