A critical challenge for autonomous underwater vehicles (AUVs) is the docking operation for applications such as sleeping under the mother ship, recharging batteries, transferring data, and new mission downloading. The final stage of docking at a unidirectional docking station requires the AUV to approach while keeping the pose (position and orientation) of the vehicle within an allowable range. The appropriate pose therefore demands a sensor unit and a control system that have high accuracy and robustness against disturbances existing in a real-world underwater environment. This paper presents a vision-based AUV docking system consisting of a 3D model-based matching method and Real-time Multi-step Genetic Algorithm (GA) for real-time estimation of the robot’s relative pose. Experiments using a remotely operated vehicle (ROV) with dual-eye cameras and a separate 3D marker were conducted in a small indoor pool. The experimental results confirmed that the proposed system is able to provide high homing accuracy and robustness against disturbances that influence not only the captured camera images but also the movement of the vehicle. A successful docking operation using stereo vision that is new and novel to the underwater vehicle environment was achieved and thus proved the effectiveness of the proposed system for AUV.