Methods, systems, and apparatus, including computer programs encoded on computer storage media, for using surfels for vehicle localization. One of the methods includes obtaining surfel data comprising a plurality of surfels, wherein each surfel corresponds to a respective different location in an environment, and each surfel has associated data that comprises a stability measure, wherein the stability measure characterizes a permanence of a surface represented by the surfel; obtaining sensor data for a plurality of locations in the environment, the sensor data having been captured by one or more sensors of a first vehicle; determining a plurality of high-stability surfels from the plurality of surfels in the surfel data; and determining a location in the environment of the first vehicle using the plurality of selected high-stability surfels and the sensor data.