A pre-fetching map data system and method identifies a subset of map data to corresponding to one or more points of interest to be displayed on the map. The map data is stored on a remote map database in map data tiles. The pre-fetching map data system identifies those map data tiles that correspond to the one or more points of interest, where the identified pre-fetch map data tiles are sent from the remote database to a client device for cache storage. The number of pre-fetch map data tiles are determined using a tile budget that is dynamically adjusted in response to changing conditions on a client device.