Near underwater structures or the surface of shallow water, acoustic sensing based navigation of autonomous underwater vehicles (AUVs) suffers from inaccurate positioning which is caused by acoustic sensing such as multi-pass and noisy data. In the paper a new underwater navigation method for AUVs is proposed based on artificial underwater landmarks which are recognized by a vision system implemented in the robot. An underwater image processing strategy and an underwater vision environment analysis method are introduced to improve reliability of the underwater vision system. Experiments were carried out to demonstrate the efficiency of the proposed navigation method of AUVs.