A map data distribution server that is connected to a network and distributes map data via the network is provided. The map data distribution server holds first map data and second map data that is of a newer version than the first map data and holds a plurality of update data including an instruction to update the first map data for each of partitions of a given size on a map. The map data distribution server decides whether a predetermined condition is fulfilled upon receiving an update request to update the first map data in a first partition out of the partitions to the second map data from a terminal communicating with the map data distribution server via the network, selects one of the plurality of update data relevant to the first partition, based on the result of the decision, and transmits the selected update data to the terminal.