The Baltic States (Estonia, Latvia and Lithuania) are three amongst the smallest gas markets in Europe. They import all the gas they consume from Russia, with whom they have difficult political relationships. A disruption of their supply from Russia, whatever the cause, would have severe consequences as a large share of their peak winter consumption could not be replaced by alternative gas or other fuels. The three governments want to invest in improving gas supply security and the European Commission pushes in the same direction. But what should they do? We present an assessment of the cost of various national and regional options - dual-fuel for heat plants and CHPs; strategic gas storage; strategic LNG terminals - to increase gas supply security. The cost is calculated over thirty years for different scenarios of supply disruptions. Uncertainty in commodity prices and interest rates is taken into account through Monte Carlo simulations. We draw the policy conclusions, taking into account the regional political context.