Aspects of the technology relate to providing service area maps for an autonomous vehicle transportation service having a fleet of vehicles. For instance, each vehicle of the fleet is associated with a polygon corresponding to a service area for that vehicle. A first location may be received from a client computing device, and a set of vehicles of the fleet of vehicles that are currently available to provide transportation services may be identified based on the first location. The polygons associated with each of the set of vehicles may be used to determine a first polygon having a geographic area. A first portion of map information corresponding to the geographic area of the first polygon may be identified, and the first portion may be provided to the client computing device for display to a user such that the portion represents a currently available service area for the user.