A map generation device according to one embodiment includes a reception unit that receives probe data transmitted from at least one vehicle and indicating a feature detected in vehicle surroundings by an environment monitoring sensor incorporated in the vehicle, and the device creates or updates map data based on the probe data received by the reception unit. The map generation device includes: a characteristic determination unit that determines whether the probe data includes sufficient characteristic information usable for alignment with other probe data or map data; and a combining unit that joins a target probe data set including an insufficient amount of characteristic information to the probe data previous or subsequent to the target probe data set in consecutive probe data sets acquired from the same travel of the same vehicle.