A shift control device for a vehicle, the vehicle including an automatic transmission, the shift control device comprising: an electronic control unit configured to: i) set a target gear stage based on data showing traveling states including at least a driving demand; ii) set a neutral state where power is not transmitted by releasing an engagement mechanism engaged such that a predetermined gear stage is set in the automatic transmission, when a predetermined condition determined in advance such that coasting is allowed is satisfied during traveling; iii) eliminate the neutral state, when the predetermined condition is not satisfied during the coasting in the neutral state, by eliminating the releasing the engagement mechanism engaged; iv) calculate a virtual gear stage, when the predetermined condition is not satisfied during the coasting in the neutral state, such that the virtual gear stage as an input rotation speed close to an input rotation speed of the automatic transmission in the neutral state, the virtual gear stage is calculated based on a vehicle speed at a time point when the virtual gear stage is calculated and a gear ratio at a gear stage allowed to be set in the automatic transmission, wherein the electronic control unit is configured to calculate the virtual gear stage such that the virtual gear stage is a gear stage having a gear ratio becoming a rotation speed close to the input rotation speed of the automatic transmission in the neutral state at a time point when the virtual gear stage is calculated and less than the input rotation speed among rotation speeds obtained as products of an output rotation speed of the automatic transmission corresponding to the vehicle speed and the gear ratio; and v) in a case where the virtual gear stage is a gear stage on a lower-speed side than a current gear stage, the current gear stage determined based on the output rotation speed of the automatic transmission, control a shift of the automatic transmission, when the neutral state is eliminated, such that a first shift from the virtual gear stage toward the current gear stage during the neutral state is initiated, and a second shift from the current gear stage toward the target gear stage is initiated during the first shift. i) set a target gear stage based on data showing traveling states including at least a driving demand; ii) set a neutral state where power is not transmitted by releasing an engagement mechanism engaged such that a predetermined gear stage is set in the automatic transmission, when a predetermined condition determined in advance such that coasting is allowed is satisfied during traveling; iii) eliminate the neutral state, when the predetermined condition is not satisfied during the coasting in the neutral state, by eliminating the releasing the engagement mechanism engaged; iv) calculate a virtual gear stage, when the predetermined condition is not satisfied during the coasting in the neutral state, such that the virtual gear stage as an input rotation speed close to an input rotation speed of the automatic transmission in the neutral state, the virtual gear stage is calculated based on a vehicle speed at a time point when the virtual gear stage is calculated and a gear ratio at a gear stage allowed to be set in the automatic transmission, wherein the electronic control unit is configured to calculate the virtual gear stage such that the virtual gear stage is a gear stage having a gear ratio becoming a rotation speed close to the input rotation speed of the automatic transmission in the neutral state at a time point when the virtual gear stage is calculated and less than the input rotation speed among rotation speeds obtained as products of an output rotation speed of the automatic transmission corresponding to the vehicle speed and the gear ratio; and v) in a case where the virtual gear stage is a gear stage on a lower-speed side than a current gear stage, the current gear stage determined based on the output rotation speed of the automatic transmission, control a shift of the automatic transmission, when the neutral state is eliminated, such that a first shift from the virtual gear stage toward the current gear stage during the neutral state is initiated, and a second shift from the current gear stage toward the target gear stage is initiated during the first shift.