The main goal of this chapter is to investigate the possibilities of optimizing the supply chain delivery service. For creating an optimal delivery service we used the method of stochastic programming. The method of stochastic programming was chosen for the reason that it allows the decision maker to explicitly analyze uncertainties and control risk. The chapter presents a comparative presentation of the optimization of delivery services using the linear programming method and the stochastic programming method. For this purpose, a computer-supported model was developed in an MS Excel spreadsheet. The main finding of this chapter points to the conclusion that stochastic programming minimizes costs by taking into account all possible scenarios in a way to achieve a robust solution. Despite their advantages and the growing and numerous uncertainties in supply chain operations, stochastic models are still not widely accepted in business practice.