A vehicle control device recognizes a second self-position, which is obtained by correcting a first self-position, and an orientation of a vehicle on a road, on which the vehicle is traveling, based on a situation around the vehicle, the first self-position, and map information, determines a steering control mode and a speed control mode of the vehicle based on the second self-position and the orientation of the vehicle, and performs automated driving by controlling the vehicle based on the determined control modes. When the vehicle is scheduled to advance from a first lane to a second lane and it is not possible to recognize a target associated with a road indicating an end point of a merging section, a determiner determines a steering angle control mode for searching for the target based on the second self-position and the orientation of the vehicle.