In a communication type navigation system that downloads maps, the present invention provides a map data transmission method that can reduce time before guiding is started. A map provision server searches for a traveling route connecting a starting place corresponding to current position information received from an on-vehicle terminal and a destination corresponding to destination information. The server generates guidance information for guiding the vehicle along the searched traveling route and generates a route vicinity map along the traveling route. The server generates traveling route information comprising the searched traveling route and the guidance information, and plural map information blocks into which the route vicinity map containing map information is divided along the traveling route, assigns transmission priority levels to the map information blocks, and transmits the map information blocks according to the transmission priority levels after transmitting the traveling route information.