The present disclosure provides a method, an apparatus, an electronic device and a storage medium for vehicle localization, which relates to the technical fields of autonomous driving, electronic map, deep learning, image processing, and the like. In the method, a computing device obtains an image descriptor map corresponding to a captured image of an external environment of a vehicle and a predicted pose of the vehicle when the captured image is captured; obtains a set of reference descriptors and a set of spatial coordinates corresponding to a set of keypoints of a reference image of the external environment; determines a plurality of sets of image descriptors corresponding to the set of spatial coordinates when the vehicle is in a plurality of candidate poses, respectively; determines a plurality of similarities between the plurality of sets of image descriptors and the set of reference descriptors; and updates the predicted pose based on the plurality of candidate poses and the plurality of similarities. Embodiments of the present disclosure can improve localization accuracy and robustness of the vehicle visual localization algorithm.