Aspects of the disclosure relate to evaluating pullovers for autonomous vehicles. In one instance, a set of potential pullover locations within a predetermined distance of a destination may be identified. Whether any of the potential pullover locations of the set include one or more of a plurality of predetermined types of regions of interest where a vehicle should not park for an extended period of time may be determined. A pullover location is identified based on the determination. The identified pullover location may be compared to a pullover location identified by autonomous vehicle control software in order to evaluate the pullover location identified by the autonomous vehicle control software.