We investigate analytically and empirically the relationship between demand uncertainty and cost behavior. We argue that with more uncertain demand, unusually high realizations of demand become more likely. Accordingly, firms will choose a higher capacity of fixed inputs when uncertainty increases in order to reduce congestion costs. Higher capacity levels imply a more rigid short-run cost structure with higher fixed and lower variable costs. We formalize this "counterintuitive" argument in a simple analytical model of capacity choice. Following this logic, we hypothesize that firms facing higher demand uncertainty have a more rigid short-run cost structure with higher fixed and lower variable costs. We test this hypothesis for the manufacturing sector using data from Compustat and the NBER-CES Industry Database. Evidence strongly supports our hypothesis for multiple cost categories in both datasets. The results are robust to alternative specifications.