A new stereo visual localization method was proposed based on generalized orthogonal iterative algorithm. Firstly, CensurE features and U-SURF descriptors were extracted, sub-pixel stereo matching were performed based on SAD method, and features between two consecutive image frames were matched using U-SURF descriptor. Then, 3D-3D motion estimation was carried out to obtain initial motion parameters in the framework of RANSAC. 3D-3D motion estimation could obtain the minimum error of Euclidean distance between 3D points. The 3D coordinates of feature points were greatly affected by noise, so the motion estimation error was large. In this paper, generalized orthogonal iterative algorithm was applied to visual stereo localization to obtain motion estimation parameters by minimising object-space collinearity error of points sensed by stereo cameras. The motion estimation error was greatly reduced because Euclidean distance error between 3D points was more affected by noise than collinearity error of points. Simulation experiment and outdoor intelligent vehicle experiment show that the proposed method can be run at real-time, and achieves a high accuracy and robustness, better than traditional methods.