Stereo camera is a very important sensor for mobile robot localization and mapping. Its consecutive images can be used to estimate the location of the robot with respect to its environment. This estimate will be fused with location estimates from other sensors for a globally optimal location estimate. In the data fusion context, it is important to compute the uncertainty of the stereo-based localization. In this paper, we propose an approach to obtain the uncertainty of localization when a correspondence-based method is used to estimate the robot pose. The computational complexity of this approach is O(n), where n is the number of corresponding image points. Experimental results shows that this approach is promising.