The operation of Combined Heat and Power (CHP) systems in liberalized electricity markets depends both on uncertain electricity prices and uncertain heat demand. In the future, uncertainty is going to increase due to the increased intermittent power induced by renewable energy sources. Therefore, the need for improved planning and bidding tools is highly important for CHP producers. This paper applies an optimal bidding model under the uncertainties of day-ahead market prices and the heat demand. The problem is formulated in a stochastic programming framework where future scenarios of the random variables are considered in order to handle the uncertainties. A case study is performed and conclusions are derived about the CHP operation and the need for heat storage.