A vehicle control device includes a traveling environment classification database configured to record traveling environment classification data in which at least one past traveling plan for autonomous driving and a traveling result of the past traveling plan are associated with each other for each preset traveling environment classification, a traveling environment classification determination unit configured to determine whether or not the traveling environment classification corresponding to a traveling environment of a host vehicle is present in the traveling environment classification database when the host vehicle travels in a map non-correspondence region during the autonomous driving, and a traveling plan generation unit configured to generate a map-less traveling plan as a traveling plan of the host vehicle in the map non-correspondence region when the traveling environment classification corresponding to the traveling environment of the host vehicle is present in the traveling environment classification database.