Super-majorities have occurred frequently in Congress but have escaped scholarly attention. This paper employs new measures of positive agenda control and a unique data set of 3,407 nontrivial bills from 1981 to 2008 to answer two questions: how did legislative leaders construct veto-proof coalitions, and what did presidents do with them? Legislative leaders, we argue, deployed procedures to expand and sustain veto-proof coalitions, despite increasing polarization. The resulting history, which signaled members' commitment to a bill, provided information to the president that reduced uncertainty about possibilities for interbranch bargaining and the likely success of a veto. We find that positive agenda control increased the probability of vote tallies of two-thirds or more, especially after the 1994 election. In addition, we demonstrate that presidents concentrated veto activity on bills with outcomes of less than two-thirds, rejected some veto-proof bills for reputational gains, and deployed signing statements strategically. The analysis suggests that congressional leaders paradoxically gained capacity for nurturing large, bipartisan alliances as the institution became more polarized. Moreover, it demonstrates that strategic activity by legislative leaders is critical to explaining variation in presidential options for veto bargaining and signing statements.