A travel control device is mounted on a vehicle including an electric motor and an internal combustion engine that are power sources and a storage battery that stores energy for driving the electric motor and regenerative energy recovered by regenerative braking of the electric motor. The travel control device includes an electronic control device configured to create a speed profile in which a speed of the vehicle is predicted, estimate a predicted amount of the regenerative energy to be recovered, based on the speed profile, and decide the power source to be used for traveling, based on the predicted amount of the regenerative energy and thermal information indicating a demand related to heat of the vehicle.