The development of high-definition (HD) maps has enabled predictive cruise control (PCC) systems to access additional road and traffic information. This study provides a novel control scheme of PCC, which utilizes HD map information. To minimize fuel consumption, the problem of the PCC is formulated as a nonlinear model predictive control, and the derivation and implementation of the fast solver are discussed. Then, a novel shift-map is proposed to define the different working regions to allow the application of the proposed PCC system. The use of the real-time HD map is discussed, and the proposed control scheme is evaluated through simulation and experimental tests. The total fuel-savings rates obtained with the PCC system and factory-installed ACC system over a 370 km route were compared. An average fuel-savings rate of as high as 8.73% can be obtained by the proposed PCC system.