Segment routing has recently received much attention in industry and academia for providing simple yet powerful and scalable traffic engineering, a most important concern for Internet Service Providers. However, the fundamental optimization problem underlying segment routing needs to be better understood today. This paper addresses this gap and presents a novel algorithmic approach to optimize traffic engineering in segment routing networks, accounting for demand uncertainty. In particular, we propose a stochastic approach to online segment routing which uses a conditional value at risk when accounting for the traffic matrix uncertainty. This approach can perform significantly better than the worst-case approach often considered in the literature. We also show that depending on the demand volatility, our stochastic approach can be further optimized in that it is sufficient to account for only a part of the demand without sacrificing traffic engineering quality.