A vehicle control device has a first calculating unit calculating a first arrival time until a vehicle reaches a lane change position where a first lane along which the vehicle is traveling and a second lane merge, or the first lane and the second lane separates, a second calculating unit calculating a second arrival time until another vehicle traveling along the second lane reaches the lane change position, and a speed control unit controlling the speed of the vehicle such that the vehicle enables to make a lane change to the second lane ahead of the other vehicle when the first arrival time is shorter than the second arrival time, and controlling the speed of the vehicle such that the vehicle enables to make a lane change to the second lane behind the other vehicle when the first arrival time is equal to or greater than the second arrival time.