In this paper, an effective probability-based tile pre-fetching algorithm and a collaborative cache replacement algorithm for Web geographical information systems(Web GISs) are proposed. The proposed tile pre-fetching algorithm can approximate which tiles will be used in advance based on the global tile access pattern of all users and the semantics of query so that a user request will be answered quickly since the needed tiles are likely in cache database. When a client runs out of cache space for newly down-loaded tiles, the proposed cache replacement algorithm determines which tiles should be replaced based on the future access probabilities. By combining the proposed tile pre-fetching algorithm with the cache replacement algorithm, the response time for user requests can be improved substantially in Web GIS systems.