We argue that the costs of bargaining failure are important determinants of legislative delay and gridlock. When these costs are high, elected officials have a greater incentive to reach legislative bargains, even if doing so means compromising on their policy objectives. We develop and evaluate this claim in the context of state budgeting, treating late budgets as examples of fiscal gridlock. Specifically, we argue that budgetary gridlock imposes political and private costs on lawmakers, the magnitudes of which are shaped by institutions and features of the political environment. Our expectations are tested and confirmed using an original dataset of the timing of budget adoption for all states over a 46-year period. Though our investigation is set in the context of the states, we show that differences in the costs of bargaining failure can also account for variation in the patterns of budgetary delay across levels of government and (to a lesser extent) variation in fiscal gridlock within the federal government.