A map matching device includes: a candidate spot extraction unit that extracts candidate spots onto a link based on position measurement points; a movement cost determination unit that determines the movement cost of a combination of links connecting one of first candidate spots extracted based on one position measurement point to one of second candidate spots extracted based on another position measurement point, the movement cost determined separately for each combination of a first and a second candidate spot; a movement possibility judgment unit that judges, for each combination of first and second candidate spots, whether a moving body can move from the first to the second candidate spot, based on the movement cost; and a matching spot determination unit that determines, as the position of the moving body on the map, one of the candidate spots included in a combination for which movement was determined to be possible.