本发明的目的在于提供一种能进行正常的地图显示和路线引导的地图信息处理装置。当地图信息储存部(16a)中不存在由位置检测单元(15)检测的自身的目前位置所对应的道路时，将该道路作为新道路。新道路检测部(19)生成表示行驶过该新道路的历史纪录的新道路行驶历史纪录信息。新道路生成部(20)基于该新道路行驶历史纪录信息生成新道路信息。新道路信息储存部(16b)储存该新道路信息。新道路编辑部(23)对于从新道路信息储存部(16b)获取的新道路信息进行编辑。道路信息更新部(21)向地图信息储存部(16a)追加由新道路信息编辑部(23)编辑的新道路信息。