A vehicle control device includes: an operation detection unit that detects an operation input of a user for an operation input unit; a speed setting unit that sets travel speed of a host vehicle on the basis of the operation input that is detected by the operation detection unit; and a lane change control unit that controls lane change. If the operation input that decreases, by more than or equal to a predetermined degree, setting travel speed that is the speed set by the speed setting unit, or the operation input that decreases the setting travel speed to be lower than current travel speed of the host vehicle, is performed after the lane change is started, the lane change control unit cancels the lane change.