This paper proposes an algorithm that is capable of localizing curbs from stereo images captured on structured roads; the proposed algorithm constructs maps sequentially for this, such as an elevation map (EM) in a u-disparity grid (UDG) using stereo disparities, probability-map of road surface based on the EM, curb-score map based on the EM and probability-map, height-change map based on the EM, and persistence-map of curb candidate cells in EM. Eventually, the algorithm estimates curbs using these maps and leads stable curb localization. The results of experiments show that the algorithm is well adapted to various road conditions.