The technology involves to pickups performed by autonomous vehicles. In particular, it includes identifying one or more potential pullover locations adjacent to an area of interest that an autonomous vehicle is approaching. The vehicle detects that a given one of the potential pullover locations is occupied by another vehicle and determines whether the other vehicle will be vacating the given pullover location within a selected amount of time. Upon determining that the other vehicle will be vacating the given potential pullover location within the timeframe, the vehicle determines whether to wait for the other vehicle to vacate the given pullover location. Then a driving system of the vehicle either performs a first action in order to wait for the other vehicle to vacate the given pullover location or performs a second action that is different from the first action when it is determined to not wait.