This paper proposes a stochastic model predictive control (MPC) approach to optimize the fuel consumption in a vehicle following context. The practical solution of that problem requires solving a constrained moving horizon optimal control problem using a short-term prediction of the preceding vehicle?s velocity. In a deterministic framework, the prediction errors lead to constraint violations and to harsh control reactions. Instead, the suggested method considers errors, and limits the probability of a constraint violation. A conditional linear Gauss model is developed and trained with real measurements to estimate the probability distribution of the future velocity of the preceding vehicle. The prediction model is used to evaluate two different stochastic MPC approaches. On the one hand, an MPC with individual chance constraints is applied. On the other hand, samples are drawn from the conditional Gaussian model and used for a scenario-based optimization approach. Finally, both developed control strategies are evaluated and compared against a standard deterministic MPC. The evaluation of the controllers shows a significant reduction of the fuel consumption compared with standard adaptive cruise control algorithms.